src/add-ons/kernel/file_systems/ramfs/BlockAllocatorArea.h

   1 // BlockAllocatorArea.h
   2
   3 #ifndef BLOCK_ALLOCATOR_AREA_H
   4 #define BLOCK_ALLOCATOR_AREA_H
   5
   6 #include <util/DoublyLinkedList.h>
   7
   8 #include "BlockAllocator.h"
   9 #include "BlockAllocatorMisc.h"
  10
  11
  12 class BlockAllocator::Area : public DoublyLinkedListLinkImpl<Area> {
  13 public:
  14         static Area *Create(size_t size);
  15         void Delete();
  16
  17         inline void SetBucket(AreaBucket *bucket)               { fBucket = bucket; }
  18         inline AreaBucket *GetBucket() const                    { return fBucket; }
  19
  20         inline Block *GetFirstBlock() const                             { return fFirstBlock; }
  21         inline Block *GetLastBlock() const                              { return fLastBlock; }
  22
  23         inline TFreeBlock *GetFirstFreeBlock() const    { return fFirstFree; }
  24         inline TFreeBlock *GetLastFreeBlock() const             { return fLastFree; }
  25
  26         inline bool IsEmpty() const                             { return (fUsedBlockCount == 0); }
  27         inline Block *GetFirstUsedBlock() const;
  28
  29         static inline size_t GetMaxFreeBytesFor(size_t areaSize);
  30
  31         inline size_t GetFreeBytes() const              { return fFreeBytes; }
  32         inline bool NeedsDefragmenting() const  { return (fFreeBlockCount > 1); }
  33
  34         inline int32 GetBucketIndex();
  35
  36         Block *AllocateBlock(size_t usableSize, bool dontDefragment = false);
  37         void FreeBlock(Block *block, bool dontDefragment = false);
  38         Block *ResizeBlock(Block *block, size_t newSize,
  39                                            bool dontDefragment = false);
  40
  41         // debugging only
  42         bool SanityCheck() const;
  43         bool CheckBlock(Block *block, size_t minSize = 0);
  44
  45 private:
  46         inline size_t _GetBlockFreeBytes()
  47                 { return fFreeBytes + sizeof(BlockHeader); }
  48
  49         Area(area_id id, size_t size);
  50         ~Area();
  51
  52         inline void _FixBlockList(Block *block, Block *prevBlock,
  53                                                           Block *nextBlock);
  54         inline void _FixFreeList(TFreeBlock *block, TFreeBlock *prevFree,
  55                                                          TFreeBlock *nextFree);
  56
  57         TFreeBlock *_FindFreeBlock(size_t minSize);
  58         void _InsertFreeBlock(TFreeBlock *block);
  59         void _RemoveFreeBlock(TFreeBlock *block);
  60         TFreeBlock * _MoveResizeFreeBlock(TFreeBlock *freeBlock, ssize_t offset,
  61                                                                           size_t newSize);
  62         inline TFreeBlock *_MakeFreeBlock(void *address, ssize_t offset,
  63                 Block *previous, size_t size, bool hasNext, TFreeBlock *previousFree,
  64                 TFreeBlock *nextFree);
  65         bool _CoalesceWithNext(TFreeBlock *block);
  66
  67         inline Block *_MakeUsedBlock(void *address, ssize_t offset,
  68                                                                  Block *previous, size_t size, bool hasNext);
  69
  70         inline bool _DefragmentingRecommended();
  71         void _Defragment();
  72
  73 private:
  74         AreaBucket                      *fBucket;
  75         area_id                         fID;
  76         size_t                          fSize;
  77         size_t                          fFreeBytes;
  78         size_t                          fFreeBlockCount;
  79         size_t                          fUsedBlockCount;
  80         Block                           *fFirstBlock;
  81         Block                           *fLastBlock;
  82         TFreeBlock                      *fFirstFree;
  83         TFreeBlock                      *fLastFree;
  84 };
  85
  86 typedef BlockAllocator::Area Area;
  87
  88
  89 // inline methods
  90
  91 // debugging
  92 #if BA_DEFINE_INLINES
  93
  94 // GetFirstUsedBlock
  95 inline
  96 Block *
  97 BlockAllocator::Area::GetFirstUsedBlock() const
  98 {
  99         // Two assumptions:
 100         // 1) There is always a first block. If that isn't so, our structure are
 101         //    corrupt.
 102         // 2) If the first block is free, the second (if any) is not. Otherwise
 103         //    there were adjoining free blocks, which our coalescing strategy
 104         //    prevents.
 105         return (fFirstBlock->IsFree() ? fFirstBlock->GetNextBlock() : fFirstBlock);
 106 }
 107
 108 // GetMaxFreeBytesFor
 109 inline
 110 size_t
 111 BlockAllocator::Area::GetMaxFreeBytesFor(size_t areaSize)
 112 {
 113         size_t headerSize = block_align_ceil(sizeof(Area));
 114         return Block::GetUsableSizeFor(block_align_floor(areaSize - headerSize));
 115 }
 116
 117 // GetBucketIndex
 118 inline
 119 int32
 120 BlockAllocator::Area::GetBucketIndex()
 121 {
 122         return bucket_containing_size(GetFreeBytes());
 123 }
 124
 125 // _FixBlockList
 126 inline
 127 void
 128 BlockAllocator::Area::_FixBlockList(Block *block, Block *prevBlock,
 129                                                                         Block *nextBlock)
 130 {
 131         if (block) {
 132                 if (prevBlock)
 133                         prevBlock->SetNextBlock(block);
 134                 else
 135                         fFirstBlock = block;
 136                 if (nextBlock)
 137                         nextBlock->SetPreviousBlock(block);
 138                 else
 139                         fLastBlock = block;
 140         }
 141 }
 142
 143 // _FixFreeList
 144 inline
 145 void
 146 BlockAllocator::Area::_FixFreeList(TFreeBlock *block, TFreeBlock *prevFree,
 147                                                                    TFreeBlock *nextFree)
 148 {
 149         if (block) {
 150                 if (prevFree)
 151                         prevFree->SetNextFreeBlock(block);
 152                 else
 153                         fFirstFree = block;
 154                 if (nextFree)
 155                         nextFree->SetPreviousFreeBlock(block);
 156                 else
 157                         fLastFree = block;
 158                 block->SetPreviousFreeBlock(prevFree);
 159                 block->SetNextFreeBlock(nextFree);
 160         }
 161 }
 162
 163 // _DefragmentingRecommended
 164 inline
 165 bool
 166 BlockAllocator::Area::_DefragmentingRecommended()
 167 {
 168         // Defragmenting Condition: At least more than 5 free blocks and
 169         // free / block ratio greater 1 / 10. Don't know, if that makes any
 170         // sense. ;-)
 171         return (fFreeBlockCount > 5 && fUsedBlockCount / fFreeBlockCount < 10);
 172 }
 173
 174 #endif  // BA_DEFINE_INLINES
 175
 176
 177 #endif  // BLOCK_ALLOCATOR_AREA_H