rom/kernel/mm_linear.h

   1 #include <exec/memory.h>
   2
   3 /*
   4  * This structure describes usable space. It is pointed to by mh_First.
   5  * start and size specify address space which can actually be used for allocations.
   6  *
   7  * map is an array describing which pages are free and which are not. It contains as
   8  * many entries as many pages there are. Every entry is a single byte which
   9  * describes page state as follows:
  10  * - Most significant bit tells if the page is free (0) or allocated (1)
  11  * - Other bits tell size of pages block to which the page belongs.
  12  * 'block' is a contiguous space of one or more pages in the same state.
  13  * Status bit of all pages in the block will have the same value (allocated or free)
  14  * and count bits will decrease from 127 to 1. 0 is not a valid value for them.
  15  * For example, free block of three pages will be described by the sequence:
  16  * 0x03, 0x02, 0x01. Allocated block of four pages will be: 0x84, 0x83, 0x82, 0x81.
  17  *
  18  * With 4K pages it gives 256 KB map size for 1GB of RAM.
  19  * For 2 MB of RAM (A1200 example) it gives 512 bytes map size. This seems to be acceptable.
  20  *
  21  * Using counter allows faster navigation in the memory map. In order to get past
  22  * the block you just add counter to the current page number. Note that the block
  23  * can be longer than 127 pages, in this case all entries where count would be >127,
  24  * will have count = 127. In this case more than one step will be required to advance
  25  * past the block. It is possible to reduce number of such steps by changing map
  26  * entries from UBYTE to UWORD or ULONG, but this will also double memory usage. So it's a
  27  * memory vs speed tradeoff.
  28  * In order to change entry size, replace five macros and typedef below.
  29  *
  30  * TODOs:
  31  * 1. Implement reverse lookup order (for MEMF_REVERSE). Find some way to optimize
  32  *    it (with current implementation it is going to be slow because we can't skip
  33  *    more than one page in reverse direction).
  34  * 2. Allow administrative information (BlockHeader and memory map) to live outside of
  35  *    managed region. This would be a nice option for managing slow memory (like A1200
  36  *    chip RAM).
  37  */
  38
  39 /* Type of map entry */
  40 typedef UBYTE page_t;
  41
  42 /* Parts of map entry */
  43 #define P_COUNT(x)  (x & 0x7F)
  44 #define P_STATUS(x) (x & 0x80)
  45
  46 /* Status bits */
  47 #define P_ALLOC 0x80
  48 #define P_FREE  0x00
  49
  50 /* Use this macro to increment pages count in the block */
  51 #define INC_COUNT(x) if (x < 127) x++
  52
  53 struct BlockHeader
  54 {
  55     struct MemChunk mc;         /* Backwards compatibility */
  56     APTR start;                 /* Start address           */
  57     ULONG size;                 /* Total size in pages     */
  58     ULONG pageSize;             /* Page size in bytes      */
  59     struct SignalSemaphore sem; /* Access semaphore        */
  60     page_t map[1];              /* Allocations map         */
  61 };