Subversion Repositories Kolibri OS

 

 

 

 

 

 

 

 

 

typedef struct memblock_s

        int             size;           // including the header and possibly tiny fragments

        int     tag;            // a tag of 0 is a free block

        int     id;                     // should be ZONEID

        struct memblock_s       *next, *prev;

        int             pad;                    // pad to 64 bit boundary

} memblock_t;

 

typedef struct

        int             size;           // total bytes malloced, including header

        memblock_t      blocklist;              // start / end cap for linked list

        memblock_t      *rover;

} memzone_t;

 

void Cache_FreeLow (int new_low_hunk);

void Cache_FreeHigh (int new_high_hunk);

 

 

 

 

 

 

 

memzone_t       *mainzone;

 

void Z_ClearZone (memzone_t *zone, int size);

 

 

void Z_ClearZone (memzone_t *zone, int size)

        memblock_t      *block;

       

 

        zone->blocklist.next = zone->blocklist.prev = block =

                (memblock_t *)( (byte *)zone + sizeof(memzone_t) );

        zone->blocklist.tag = 1;        // in use block

        zone->blocklist.id = 0;

        zone->blocklist.size = 0;

        zone->rover = block;

       

        block->prev = block->next = &zone->blocklist;

        block->tag = 0;                 // free block

        block->id = ZONEID;

        block->size = size - sizeof(memzone_t);

 

 

void Z_Free (void *ptr)

        memblock_t      *block, *other;

       

        if (!ptr)

                Sys_Error ("Z_Free: NULL pointer");

 

        block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));

        if (block->id != ZONEID)

                Sys_Error ("Z_Free: freed a pointer without ZONEID");

        if (block->tag == 0)

                Sys_Error ("Z_Free: freed a freed pointer");

 

        block->tag = 0;         // mark as free

       

        other = block->prev;

        if (!other->tag)

        {       // merge with previous free block

                other->size += block->size;

                other->next = block->next;

                other->next->prev = other;

                if (block == mainzone->rover)

                        mainzone->rover = other;

                block = other;

        }

       

        other = block->next;

        if (!other->tag)

        {       // merge the next free block onto the end

                block->size += other->size;

                block->next = other->next;

                block->next->prev = block;

                if (other == mainzone->rover)

                        mainzone->rover = block;

        }

 

 

void *Z_Malloc (int size)

        void    *buf;

       

Z_CheckHeap (); // DEBUG

        buf = Z_TagMalloc (size, 1);

        if (!buf)

                Sys_Error ("Z_Malloc: failed on allocation of %i bytes",size);

        Q_memset (buf, 0, size);

 

        return buf;

 

void *Z_TagMalloc (int size, int tag)

        int             extra;

        memblock_t      *start, *rover, *new, *base;

 

        if (!tag)

                Sys_Error ("Z_TagMalloc: tried to use a 0 tag");

 

        size += sizeof(memblock_t);     // account for size of block header

        size += 4;                                      // space for memory trash tester

        size = (size + 7) & ~7;         // align to 8-byte boundary

       

        base = rover = mainzone->rover;

        start = base->prev;

       

        do

        {

                if (rover == start)     // scaned all the way around the list

                        return NULL;

                if (rover->tag)

                        base = rover = rover->next;

                else

                        rover = rover->next;

        } while (base->tag || base->size < size);

       

        extra = base->size - size;

        if (extra >  MINFRAGMENT)

        {       // there will be a free fragment after the allocated block

                new = (memblock_t *) ((byte *)base + size );

                new->size = extra;

                new->tag = 0;                   // free block

                new->prev = base;

                new->id = ZONEID;

                new->next = base->next;

                new->next->prev = new;

                base->next = new;

                base->size = size;

        }

       

        base->tag = tag;                                // no longer a free block

       

        mainzone->rover = base->next;   // next allocation will start looking here

       

        base->id = ZONEID;

 

        *(int *)((byte *)base + base->size - 4) = ZONEID;

 

        return (void *) ((byte *)base + sizeof(memblock_t));

 

 

void Z_Print (memzone_t *zone)

        memblock_t      *block;

       

        Con_Printf ("zone size: %i  location: %p\n",mainzone->size,mainzone);

       

        for (block = zone->blocklist.next ; ; block = block->next)

        {

                Con_Printf ("block:%p    size:%7i    tag:%3i\n",

                        block, block->size, block->tag);

               

                if (block->next == &zone->blocklist)

                        break;                  // all blocks have been hit    

                if ( (byte *)block + block->size != (byte *)block->next)

                        Con_Printf ("ERROR: block size does not touch the next block\n");

                if ( block->next->prev != block)

                        Con_Printf ("ERROR: next block doesn't have proper back link\n");

                if (!block->tag && !block->next->tag)

                        Con_Printf ("ERROR: two consecutive free blocks\n");

        }

 

 

void Z_CheckHeap (void)

        memblock_t      *block;

       

        for (block = mainzone->blocklist.next ; ; block = block->next)

        {

                if (block->next == &mainzone->blocklist)

                        break;                  // all blocks have been hit    

                if ( (byte *)block + block->size != (byte *)block->next)

                        Sys_Error ("Z_CheckHeap: block size does not touch the next block\n");

                if ( block->next->prev != block)

                        Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n");

                if (!block->tag && !block->next->tag)

                        Sys_Error ("Z_CheckHeap: two consecutive free blocks\n");

        }

 

 

 

typedef struct

        int             sentinal;

        int             size;           // including sizeof(hunk_t), -1 = not allocated

        char    name[8];

} hunk_t;

 

byte    *hunk_base;

int             hunk_size;

 

int             hunk_low_used;

int             hunk_high_used;

 

qboolean        hunk_tempactive;

int             hunk_tempmark;

 

void R_FreeTextures (void);

 

 

void Hunk_Check (void)

        hunk_t  *h;

       

        for (h = (hunk_t *)hunk_base ; (byte *)h != hunk_base + hunk_low_used ; )

        {

                if (h->sentinal != HUNK_SENTINAL)

                        Sys_Error ("Hunk_Check: trahsed sentinal");

                if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)

                        Sys_Error ("Hunk_Check: bad size");

                h = (hunk_t *)((byte *)h+h->size);

        }

 

 

void Hunk_Print (qboolean all)

        hunk_t  *h, *next, *endlow, *starthigh, *endhigh;

        int             count, sum;

        int             totalblocks;

        char    name[9];

 

        name[8] = 0;

        count = 0;

        sum = 0;

        totalblocks = 0;

       

        h = (hunk_t *)hunk_base;

        endlow = (hunk_t *)(hunk_base + hunk_low_used);

        starthigh = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);

        endhigh = (hunk_t *)(hunk_base + hunk_size);

 

        Con_Printf ("          :%8i total hunk size\n", hunk_size);

        Con_Printf ("-------------------------\n");

 

        while (1)

        {

        //

        // skip to the high hunk if done with low hunk

        //

                if ( h == endlow )

                {

                        Con_Printf ("-------------------------\n");

                        Con_Printf ("          :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used);

                        Con_Printf ("-------------------------\n");

                        h = starthigh;

                }

               

        //

        // if totally done, break

        //

                if ( h == endhigh )

                        break;

 

        //

        // run consistancy checks

        //

                if (h->sentinal != HUNK_SENTINAL)

                        Sys_Error ("Hunk_Check: trahsed sentinal");

                if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)

                        Sys_Error ("Hunk_Check: bad size");

                       

                next = (hunk_t *)((byte *)h+h->size);

                count++;

                totalblocks++;

                sum += h->size;

 

        //

        // print the single block

        //

                memcpy (name, h->name, 8);

                if (all)

                        Con_Printf ("%8p :%8i %8s\n",h, h->size, name);

                       

        //

        // print the total

        //

                if (next == endlow || next == endhigh ||

                strncmp (h->name, next->name, 8) )

                {

                        if (!all)

                                Con_Printf ("          :%8i %8s (TOTAL)\n",sum, name);

                        count = 0;

                        sum = 0;

                }

 

                h = next;

        }

 

        Con_Printf ("-------------------------\n");

        Con_Printf ("%8i total blocks\n", totalblocks);

       

 

void *Hunk_AllocName (int size, char *name)

        hunk_t  *h;

       

        Hunk_Check ();

 

        if (size < 0)

                Sys_Error ("Hunk_Alloc: bad size: %i", size);

               

        size = sizeof(hunk_t) + ((size+15)&~15);

       

        if (hunk_size - hunk_low_used - hunk_high_used < size)

                Sys_Error ("Hunk_Alloc: failed on %i bytes",size);

       

        h = (hunk_t *)(hunk_base + hunk_low_used);

        hunk_low_used += size;

 

        Cache_FreeLow (hunk_low_used);

 

        memset (h, 0, size);

       

        h->size = size;

        h->sentinal = HUNK_SENTINAL;

        Q_strncpy (h->name, name, 8);

       

        return (void *)(h+1);

 

void *Hunk_Alloc (int size)

        return Hunk_AllocName (size, "unknown");

 

int     Hunk_LowMark (void)

        return hunk_low_used;

 

void Hunk_FreeToLowMark (int mark)

        if (mark < 0 || mark > hunk_low_used)

                Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark);

        memset (hunk_base + mark, 0, hunk_low_used - mark);

        hunk_low_used = mark;

 

int     Hunk_HighMark (void)

        if (hunk_tempactive)

        {

                hunk_tempactive = false;

                Hunk_FreeToHighMark (hunk_tempmark);

        }

 

        return hunk_high_used;

 

void Hunk_FreeToHighMark (int mark)

        if (hunk_tempactive)

        {

                hunk_tempactive = false;

                Hunk_FreeToHighMark (hunk_tempmark);

        }

        if (mark < 0 || mark > hunk_high_used)

                Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark);

        memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark);

        hunk_high_used = mark;

 

 

void *Hunk_HighAllocName (int size, char *name)

        hunk_t  *h;

 

        if (size < 0)

                Sys_Error ("Hunk_HighAllocName: bad size: %i", size);

 

        if (hunk_tempactive)

        {

                Hunk_FreeToHighMark (hunk_tempmark);

                hunk_tempactive = false;

        }

 

        Hunk_Check ();

 

        size = sizeof(hunk_t) + ((size+15)&~15);

 

        if (hunk_size - hunk_low_used - hunk_high_used < size)

        {

                Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size);

                return NULL;

        }

 

        hunk_high_used += size;

        Cache_FreeHigh (hunk_high_used);

 

        h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);

 

        memset (h, 0, size);

        h->size = size;

        h->sentinal = HUNK_SENTINAL;

        Q_strncpy (h->name, name, 8);

 

        return (void *)(h+1);

 

 

 

void *Hunk_TempAlloc (int size)

        void    *buf;

 

        size = (size+15)&~15;

       

        if (hunk_tempactive)

        {

                Hunk_FreeToHighMark (hunk_tempmark);

                hunk_tempactive = false;

        }

       

        hunk_tempmark = Hunk_HighMark ();

 

        buf = Hunk_HighAllocName (size, "temp");

 

        hunk_tempactive = true;

 

        return buf;

 

 

 

 

typedef struct cache_system_s

        int                                             size;           // including this header

        cache_user_t                    *user;

        char                                    name[16];

        struct cache_system_s   *prev, *next;

        struct cache_system_s   *lru_prev, *lru_next;   // for LRU flushing    

} cache_system_t;

 

cache_system_t *Cache_TryAlloc (int size, qboolean nobottom);

 

cache_system_t  cache_head;

 

void Cache_Move ( cache_system_t *c)

        cache_system_t          *new;

 

        new = Cache_TryAlloc (c->size, true);

        if (new)

        {

 

                Q_memcpy ( new+1, c+1, c->size - sizeof(cache_system_t) );

                new->user = c->user;

                Q_memcpy (new->name, c->name, sizeof(new->name));

                Cache_Free (c->user);

                new->user->data = (void *)(new+1);

        }

        else

        {

 

                Cache_Free (c->user);           // tough luck...

        }

 

 

void Cache_FreeLow (int new_low_hunk)

        cache_system_t  *c;

       

        while (1)

        {

                c = cache_head.next;

                if (c == &cache_head)

                        return;         // nothing in cache at all

                if ((byte *)c >= hunk_base + new_low_hunk)

                        return;         // there is space to grow the hunk

                Cache_Move ( c );       // reclaim the space

        }

 

 

void Cache_FreeHigh (int new_high_hunk)

        cache_system_t  *c, *prev;

       

        prev = NULL;

        while (1)

        {

                c = cache_head.prev;

                if (c == &cache_head)

                        return;         // nothing in cache at all

                if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk)

                        return;         // there is space to grow the hunk

                if (c == prev)

                        Cache_Free (c->user);   // didn't move out of the way

                else

                {

                        Cache_Move (c); // try to move it

                        prev = c;

                }

        }

 

void Cache_UnlinkLRU (cache_system_t *cs)

        if (!cs->lru_next || !cs->lru_prev)

                Sys_Error ("Cache_UnlinkLRU: NULL link");

 

        cs->lru_next->lru_prev = cs->lru_prev;

        cs->lru_prev->lru_next = cs->lru_next;

       

        cs->lru_prev = cs->lru_next = NULL;

 

void Cache_MakeLRU (cache_system_t *cs)

        if (cs->lru_next || cs->lru_prev)

                Sys_Error ("Cache_MakeLRU: active link");

 

        cache_head.lru_next->lru_prev = cs;

        cs->lru_next = cache_head.lru_next;

        cs->lru_prev = &cache_head;

        cache_head.lru_next = cs;

 

 

cache_system_t *Cache_TryAlloc (int size, qboolean nobottom)

        cache_system_t  *cs, *new;

       

 

        if (!nobottom && cache_head.prev == &cache_head)

        {

                if (hunk_size - hunk_high_used - hunk_low_used < size)

                        Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size);

 

                new = (cache_system_t *) (hunk_base + hunk_low_used);

                memset (new, 0, sizeof(*new));

                new->size = size;

 

                cache_head.prev = cache_head.next = new;

                new->prev = new->next = &cache_head;

               

                Cache_MakeLRU (new);

                return new;

        }

       

 

        new = (cache_system_t *) (hunk_base + hunk_low_used);

        cs = cache_head.next;

       

        do

        {

                if (!nobottom || cs != cache_head.next)

                {

                        if ( (byte *)cs - (byte *)new >= size)

                        {       // found space

                                memset (new, 0, sizeof(*new));

                                new->size = size;

                               

                                new->next = cs;

                                new->prev = cs->prev;

                                cs->prev->next = new;

                                cs->prev = new;

                               

                                Cache_MakeLRU (new);

       

                                return new;

                        }

                }

 

        // continue looking            

                new = (cache_system_t *)((byte *)cs + cs->size);

                cs = cs->next;

 

        } while (cs != &cache_head);

       

        if ( hunk_base + hunk_size - hunk_high_used - (byte *)new >= size)

        {

                memset (new, 0, sizeof(*new));

                new->size = size;

               

                new->next = &cache_head;

                new->prev = cache_head.prev;

                cache_head.prev->next = new;

                cache_head.prev = new;

               

                Cache_MakeLRU (new);

 

                return new;

        }

       

        return NULL;            // couldn't allocate

 

 

void Cache_Flush (void)

        while (cache_head.next != &cache_head)

                Cache_Free ( cache_head.next->user );   // reclaim the space

 

 

 

void Cache_Print (void)

        cache_system_t  *cd;

 

        for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next)

        {

                Con_Printf ("%8i : %s\n", cd->size, cd->name);

        }

 

 

void Cache_Report (void)

        Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) );

 

 

void Cache_Compact (void)

 

 

void Cache_Init (void)

        cache_head.next = cache_head.prev = &cache_head;

        cache_head.lru_next = cache_head.lru_prev = &cache_head;

 

        Cmd_AddCommand ("flush", Cache_Flush);

 

 

void Cache_Free (cache_user_t *c)

        cache_system_t  *cs;

 

        if (!c->data)

                Sys_Error ("Cache_Free: not allocated");

 

        cs = ((cache_system_t *)c->data) - 1;

 

        cs->prev->next = cs->next;

        cs->next->prev = cs->prev;

        cs->next = cs->prev = NULL;

 

        c->data = NULL;

 

        Cache_UnlinkLRU (cs);

 

 

 

void *Cache_Check (cache_user_t *c)

        cache_system_t  *cs;

 

        if (!c->data)

                return NULL;

 

        cs = ((cache_system_t *)c->data) - 1;

 

        Cache_UnlinkLRU (cs);

        Cache_MakeLRU (cs);

       

        return c->data;

 

 

void *Cache_Alloc (cache_user_t *c, int size, char *name)

        cache_system_t  *cs;

 

        if (c->data)

                Sys_Error ("Cache_Alloc: allready allocated");

       

        if (size <= 0)

                Sys_Error ("Cache_Alloc: size %i", size);

 

        size = (size + sizeof(cache_system_t) + 15) & ~15;

 

        while (1)

        {

                cs = Cache_TryAlloc (size, false);

                if (cs)

                {

                        strncpy (cs->name, name, sizeof(cs->name)-1);

                        c->data = (void *)(cs+1);

                        cs->user = c;

                        break;

                }

       

        // free the least recently used cahedat

                if (cache_head.lru_prev == &cache_head)

                        Sys_Error ("Cache_Alloc: out of memory");

                                                                                                        // not enough memory at all

                Cache_Free ( cache_head.lru_prev->user );

        }

       

        return Cache_Check (c);

 

 

 

void Memory_Init (void *buf, int size)

        int p;

        int zonesize = DYNAMIC_SIZE;

 

        hunk_base = buf;

        hunk_size = size;

        hunk_low_used = 0;

        hunk_high_used = 0;

       

        Cache_Init ();

        p = COM_CheckParm ("-zone");

        if (p)

        {

                if (p < com_argc-1)

                        zonesize = Q_atoi (com_argv[p+1]) * 1024;

                else

                        Sys_Error ("Memory_Init: you must specify a size in KB after -zone");

        }

        mainzone = Hunk_AllocName (zonesize, "zone" );

        Z_ClearZone (mainzone, zonesize);