rom/kernel/mm_linear.h

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