1/*---------------------------------------------------------------------------
2|   Copyright (C) 1999-2000  Jochen C. Loewer (loewerj@hotmail.com)
3+----------------------------------------------------------------------------
4|
5|   $Id: domalloc.c,v 1.10 2007/08/18 00:33:12 rolf Exp $
6|
7|
8|   A special memory allocator, which uses pre-allocated / bit masked
9|   based administration of memory blocks with fixed sizes, like
10|   DOM nodes. This will hopefully save some memory.
11|
12|
13|   The contents of this file are subject to the Mozilla Public License
14|   Version 1.1 (the "License"); you may not use this file except in
15|   compliance with the License. You may obtain a copy of the License at
16|   http://www.mozilla.org/MPL/
17|
18|   Software distributed under the License is distributed on an "AS IS"
19|   basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
20|   License for the specific language governing rights and limitations
21|   under the License.
22|
23|   The Original Code is tDOM.
24|
25|   The Initial Developer of the Original Code is Jochen Loewer
26|   Portions created by Jochen Loewer are Copyright (C) 1998, 1999
27|   Jochen Loewer. All Rights Reserved.
28|
29|   Contributor(s):
30|
31|
32|   written by Jochen Loewer
33|   October, 2000
34|
35\--------------------------------------------------------------------------*/
36
37/*---------------------------------------------------------------------------
38|   Includes
39|
40\--------------------------------------------------------------------------*/
41#include <tcl.h>
42#include <stdlib.h>
43#include <string.h>
44#include <domalloc.h>
45
46
47/*---------------------------------------------------------------------------
48|   Defines
49|
50\--------------------------------------------------------------------------*/
51#define DBG(x)
52#define MAX_BINS         256
53#define BIN_HASH_SIZE    512
54#define BIN_HASH_MASK    0x01FF
55#define CACHE_SIZE       4
56#define BLOCK_DATA_SIZE  31000
57#define BLOCK_SIZE_BITS  16
58
59
60/*---------------------------------------------------------------------------
61|   Typedefs
62|
63\--------------------------------------------------------------------------*/
64typedef struct domAllocBlock {
65    struct domAllocBin    * bin;
66    void                  * end;
67    struct domAllocBlock  * prev;
68    struct domAllocBlock  * next;
69    int                     hashIndex1;
70    struct domAllocBlock  * hashNext1;
71    int                     hashIndex2;
72    struct domAllocBlock  * hashNext2;
73    int                     slots;
74    int                     freeSlots;
75    int                     bitmaps;
76    int                     freePos;
77    int                     freeBit;
78    unsigned int            freeMask;
79} domAllocBlock;
80
81
82typedef struct domAllocBin {
83    int                     size;
84    int                     nrSlots;
85    int                     freeSlots;
86    int                     nrBlocks;
87    domAllocBlock         * freeBlocks;
88    domAllocBlock         * usedBlocks;
89} domAllocBin;
90
91
92typedef struct domAllocBins {
93    struct domAllocBin   * bin[MAX_BINS];
94    struct domAllocBlock * hashedBlocks[BIN_HASH_SIZE];
95    struct domAllocBlock * blockCache[CACHE_SIZE];
96} domAllocBins;
97
98
99/*---------------------------------------------------------------------------
100|   Globals. This is a "single-threaded" allocator.
101|
102\--------------------------------------------------------------------------*/
103static domAllocBins bins;
104
105#ifdef TCL_THREADS
106# define TDomThreaded(x) x
107  static Tcl_Mutex binMutex;
108#else
109# define TDomThreaded(x)
110#endif
111
112/*---------------------------------------------------------------------------
113|   domAllocInit
114|
115\--------------------------------------------------------------------------*/
116void
117domAllocInit()
118{
119    int i;
120
121    DBG(fprintf(stderr, "domAllocInit...\n");)
122
123    for (i=0; i < MAX_BINS;      i++) bins.bin[i]          = NULL;
124    for (i=0; i < CACHE_SIZE;    i++) bins.blockCache[i]   = NULL;
125    for (i=0; i < BIN_HASH_SIZE; i++) bins.hashedBlocks[i] = NULL;
126}
127
128
129/*--------------------------------------------------------------------------
130|   fillHashTable
131|
132\--------------------------------------------------------------------------*/
133static void
134fillHashTable (
135    domAllocBlock  * block,
136    void           * mem
137)
138{
139    domAllocBlock * hashedBlock;
140    unsigned int    i;
141
142    i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK;
143    hashedBlock = bins.hashedBlocks[i];
144    while (hashedBlock != NULL) {
145        if (hashedBlock == block) {
146            /* all is fine, block is already in hash table */
147            return;
148        }
149        if      (hashedBlock->hashIndex1 == (int)i) hashedBlock = hashedBlock->hashNext1;
150        else if (hashedBlock->hashIndex2 == (int)i) hashedBlock = hashedBlock->hashNext2;
151        else hashedBlock = NULL;
152    }
153
154    /* add block in hash table */
155    if (block->hashIndex1 == -1) {
156        block->hashIndex1 = i;
157        block->hashNext1  = bins.hashedBlocks[i];
158    } else
159    if (block->hashIndex2 == -1) {
160        block->hashIndex2 = i;
161        block->hashNext2  = bins.hashedBlocks[i];
162    } else {
163        DBG(
164            fprintf(stderr, "\ntoo many hash entries for %x %x->%d %d,%d!\n",
165                    (unsigned int)block,
166                    (unsigned int)mem, i, block->hashIndex1, block->hashIndex2);)
167    }
168    bins.hashedBlocks[i] = block;
169}
170
171/*--------------------------------------------------------------------------
172|   domAlloc
173|
174\--------------------------------------------------------------------------*/
175void *
176domAlloc (
177    int  size
178)
179{
180    domAllocBin   * bin;
181    domAllocBlock * block;
182    domAllocBlock * hashedBlock;
183    int             i, j, slots, bitmaps, blockSize;
184    unsigned int    mask;
185    char          * mem;
186    unsigned int  * usedBitmap;
187
188
189    DBG(fprintf(stderr, "\ndomAlloc %d \n", size);)
190
191    if (size >= MAX_BINS) {
192        DBG(fprintf(stderr, "\nSize too large as used for bin!\n");)
193        return NULL;
194    }
195
196    /*-------------------------------------------------
197     |   FIXME
198     |
199     |   Rewrite with TSD-based bins to avoid mutex
200     |   contention. Threads are going to step on
201     |   each other toes here which is not what we
202     |   would like to have, don't we ?  (zv)
203     \------------------------------------------------*/
204
205    TDomThreaded(Tcl_MutexLock(&binMutex);) /* LOCK !*/
206
207    if (bins.bin[size] == NULL) {
208        /*-------------------------------------------------
209        |   create new bin
210        \------------------------------------------------*/
211        bin = (domAllocBin *)malloc(sizeof(domAllocBin));
212        bin->size        = size;
213        bin->nrSlots     = 0;
214        bin->freeSlots   = 0;
215        bin->nrBlocks    = 0;
216        bin->freeBlocks  = NULL;
217        bin->usedBlocks  = NULL;
218
219        bins.bin[size] = bin;
220
221    } else {
222        bin = bins.bin[size];
223    }
224
225    if (bin->freeSlots == 0) {
226        DBG(fprintf(stderr, "allocating new block ... \n");)
227        /*----------------------------------------------------------------
228        |   allocate and initialize a new block
229        |
230        \---------------------------------------------------------------*/
231        bitmaps   = (BLOCK_DATA_SIZE  / size) / 32;
232        slots     = bitmaps * 32;
233        blockSize = sizeof(domAllocBlock) + bitmaps*4 + slots*size;
234
235        block = (domAllocBlock *)malloc( blockSize );
236        block->bin        = bin;
237        block->end        = (char*)block + blockSize;
238        block->slots      = slots;
239        block->freeSlots  = slots;
240        block->bitmaps    = bitmaps;
241        block->freePos    = 0;
242        block->freeBit    = 0;
243        block->freeMask   = 0x80000000;
244        block->hashIndex1 = -1;
245        block->hashNext1  = NULL;
246        block->hashIndex2 = -1;
247        block->hashNext2  = NULL;
248
249        usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
250        memset(usedBitmap, 0, bitmaps * 4);
251
252        bin->nrSlots   += slots;
253        bin->freeSlots += slots;
254        bin->nrBlocks++;
255
256        block->prev     = NULL;            /* prepend this new block to free list */
257        block->next     = bin->freeBlocks;
258        bin->freeBlocks = block;
259
260        /*---------------------------------------------------------
261        |   enter block in 'hash' table:
262        |     first and last memory location could have different
263        |     hash entries due to different upper address bits
264        \--------------------------------------------------------*/
265        mem = (char*)usedBitmap + bitmaps * 4;
266        fillHashTable (block, mem);
267        mem += (slots-1) * size;
268        fillHashTable (block, mem);
269
270    } else {
271        block = bin->freeBlocks;
272    }
273
274    /*------------------------------------------------------------------------
275    |   find free slot in (partial) free block
276    |
277    \-----------------------------------------------------------------------*/
278    usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
279    i    = block->freePos;  /* start at old pos to quickly find a free slot */
280    j    = block->freeBit;
281    mask = block->freeMask;
282    do {
283        DBG(fprintf(stderr, "looking %d slot i=%d j=%d %x mask %x\n",
284                                        size, i, j, usedBitmap[i], mask); )
285        if (usedBitmap[i] != 0xFFFFFFFF) {
286            do {
287                if ((usedBitmap[i] & mask)==0) {
288                    DBG(fprintf(stderr, "found free slot i=%d j=%d %x mask %x\n",
289                                        i, j, usedBitmap[i], mask); )
290                    mem = ((char*)usedBitmap) + (4*block->bitmaps) + ((i*32)+j) * size;
291                    usedBitmap[i] |= mask;
292                    block->freeSlots--;
293                    bin->freeSlots--;
294                    if (block->freeSlots == 0) {
295                        DBG(fprintf(stderr, "freeSlots == 0\n");)
296
297                        if (block->prev == NULL) {      /* remove block from free list */
298                            bin->freeBlocks   = block->next;
299                        } else {
300                            block->prev->next = block->next;
301                        }
302                        if (block->next) block->next->prev = block->prev;
303
304                        block->next     = bin->usedBlocks;  /* add block to used list */
305                        if (block->next) block->next->prev = block;
306                        block->prev     = NULL;
307                        bin->usedBlocks = block;
308
309                        /* check consistency */
310                        hashedBlock = block->bin->freeBlocks;
311                        while (hashedBlock) {
312                            if (hashedBlock == block) {
313                                DBG(fprintf(stderr, "strange block still in free list \n");)
314                            }
315                            hashedBlock = hashedBlock->next;
316                        }
317
318                    }
319                    /* keep found free position for later,
320                     * so that next slots can be found quickly
321                     */
322                    block->freePos  = i;
323                    j++; mask = mask >> 1;
324                    if (j >= 32) { j = 0; mask = 0x80000000; }
325                    block->freeBit  = j;
326                    block->freeMask = mask;
327
328                    TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/
329                    return mem;
330                }
331                j++; mask = mask >> 1;
332                if (j >= 32) { j = 0; mask = 0x80000000; }
333            } while (j != block->freeBit);
334        }
335        i++;
336        if (i >= block->bitmaps) i = 0;
337    } while (i != block->freePos);
338
339    /* TDomThreaded(Tcl_MutexUnlock(&binMutex);) */
340
341    DBG(fprintf(stderr, "\ndomAlloc: can't happen! \n");)
342    *((char*)0) = 0; /* Use Tcl_Panic() for this ? */
343    return NULL;
344}
345
346
347/*---------------------------------------------------------------------------
348|   domFree
349|
350\--------------------------------------------------------------------------*/
351void
352domFree (
353    void  * mem
354)
355{
356    domAllocBlock * block;
357    domAllocBlock * hashedBlock;
358    domAllocBlock * prevBlock;
359    int             slotNr, i, foundInCache;
360    unsigned int  * usedBitmap;
361    unsigned int    mask;
362
363    DBG(fprintf(stderr, "domFree...\n");)
364
365    if (mem == NULL) return;
366
367    /*-------------------------------------------------
368     |   FIXME (see domAlloc comments)
369     |
370     \------------------------------------------------*/
371
372    TDomThreaded(Tcl_MutexLock(&binMutex);)
373
374    /*-------------------------------------------------------------------
375    |   Find the block, which corresponds to the given memory location
376    |
377    |   - First try to look in the memory range cache.
378    |
379    \------------------------------------------------------------------*/
380    block = NULL;
381    foundInCache = 0;
382    for (i=0; i < CACHE_SIZE; i++) {
383        if ((bins.blockCache[i] != NULL) &&
384            (mem > (void*)(bins.blockCache[i])) &&
385            (mem < (void*)(bins.blockCache[i]->end))) {
386           block = bins.blockCache[i];
387           foundInCache = 1;
388           break;
389        }
390    }
391    /*-------------------------------------------------------------------
392    |   - Otherwise try to lookup corresponding block in hashtable
393    |
394    \------------------------------------------------------------------*/
395    if (!foundInCache) {
396        i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK;
397        block = bins.hashedBlocks[i];
398        while (block != NULL) {
399            if ((mem > (void*)block) && (mem < (void*)(block->end))) break;
400            if      (block->hashIndex1 == i) block = block->hashNext1;
401            else if (block->hashIndex2 == i) block = block->hashNext2;
402            else block = NULL;
403        }
404    }
405
406    if (block == NULL) {
407        DBG(fprintf(stderr, "\n unable to free mem %x !\n", (unsigned int)mem);)
408        TDomThreaded(Tcl_MutexUnlock(&binMutex);)
409        return;
410    }
411
412    /*-------------------------------------------------------------------
413    |   clear the allocation bit
414    \------------------------------------------------------------------*/
415    usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock));
416    slotNr = ( (char*)mem - (char*)usedBitmap - block->bitmaps*4 ) / block->bin->size;
417    DBG(
418    if (slotNr >= block->slots) {
419        fprintf(stderr, "assertion failed: slotNr = %d \n", slotNr);
420    })
421    i = slotNr >> 5 ;  /* slotNr / 32 */
422    mask = 0x80000000 >> (slotNr % 32);
423    usedBitmap[i] &= ~mask;
424    block->freeSlots++;
425    block->bin->freeSlots++;
426
427    DBG(
428    if ((block->freeSlots < 1) || (block->freeSlots > block->slots)) {
429        fprintf(stderr, "assertion failed: freeSlots = %d \n", block->freeSlots);
430    })
431
432    /*-------------------------------------------------------------------
433    |   update free/used lists
434    \------------------------------------------------------------------*/
435    if (block->freeSlots == 1) {
436        if (block->prev == NULL) {      /* remove block from used list */
437            block->bin->usedBlocks = block->next;
438        } else {
439            block->prev->next = block->next;
440        }
441        if (block->next) block->next->prev = block->prev;
442
443        block->next            = block->bin->freeBlocks;  /* add block to free list */
444        if (block->next) block->next->prev = block;
445        block->prev            = NULL;
446        block->bin->freeBlocks = block;
447
448        DBG(
449        /* check consistency */
450        hashedBlock = block->bin->usedBlocks;
451        while (hashedBlock) {
452            if (hashedBlock == block) {
453                fprintf(stderr, "strange block still in used list \n");
454            }
455            hashedBlock = hashedBlock->next;
456        }
457        )
458    }
459
460    /*-------------------------------------------------------------------
461    |   free the whole block, when all slots are freed
462    \------------------------------------------------------------------*/
463    if (block->freeSlots == block->slots) {
464
465        DBG(fprintf(stderr, "block completely freed %x\n",
466                             (unsigned int)block);)
467
468        if (block->prev == NULL) {      /* remove block from free list */
469            block->bin->freeBlocks = block->next;
470        } else {
471            block->prev->next = block->next;
472        }
473        if (block->next) block->next->prev = block->prev;
474
475        block->bin->nrSlots   -= block->slots;
476        block->bin->freeSlots -= block->slots;
477        block->bin->nrBlocks--;
478
479        /*--------------------------------------------------------------------
480        |   remove block from (two) hash lists
481        \-------------------------------------------------------------------*/
482        i = block->hashIndex1;
483        if (i != -1) {
484            DBG(fprintf(stderr, "remove from hash list %d \n", i);)
485            prevBlock = NULL;
486            hashedBlock = bins.hashedBlocks[i];
487            while (hashedBlock) {
488                if (hashedBlock == block) break;
489                prevBlock = hashedBlock;
490                if      (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
491                else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
492                else hashedBlock = NULL;
493            }
494            if (prevBlock == NULL) {
495                bins.hashedBlocks[i] = block->hashNext1;
496            } else {
497                if      (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext1;
498                else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext1;
499            }
500        }
501        i = block->hashIndex2;
502        if (i != -1) {
503            DBG(fprintf(stderr, "remove from hash list %d \n", i);)
504            prevBlock = NULL;
505            hashedBlock = bins.hashedBlocks[i];
506            while (hashedBlock) {
507                if (hashedBlock == block) break;
508                prevBlock = hashedBlock;
509                if      (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
510                else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
511                else hashedBlock = NULL;
512            }
513            if (prevBlock == NULL) {
514                bins.hashedBlocks[i] = block->hashNext2;
515            } else {
516                if      (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext2;
517                else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext2;
518            }
519        }
520
521        /*------------------------------------------------------
522        |   remove block from cache, if found
523        \-----------------------------------------------------*/
524        for (i=0; i < CACHE_SIZE; i++) {
525            if (bins.blockCache[i] == block) {
526                bins.blockCache[i] = NULL;
527            }
528        }
529
530        DBG(
531        /* check consistency */
532        for (i=0; i < block->bitmaps; i++) {
533            if (usedBitmap[i] != 0) {
534                fprintf(stderr, "strange bitmap %d is %x \n", i, usedBitmap[i]);
535            }
536        }
537        for (i=0; i < BIN_HASH_SIZE; i++) {
538            hashedBlock = bins.hashedBlocks[i];
539            while (hashedBlock) {
540                if (hashedBlock == block) {
541                    fprintf(stderr, "strange block %d still in hash table \n", i);
542                }
543                if      (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1;
544                else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2;
545                else hashedBlock = NULL;
546            }
547        }
548        hashedBlock = block->bin->freeBlocks;
549        while (hashedBlock) {
550            if (hashedBlock == block) {
551                fprintf(stderr, "strange block still in free list \n");
552            }
553            hashedBlock = hashedBlock->next;
554        }
555        hashedBlock = block->bin->usedBlocks;
556        while (hashedBlock) {
557            if (hashedBlock == block) {
558                fprintf(stderr, "strange block still in used list \n");
559            }
560            hashedBlock = hashedBlock->next;
561        }
562        )
563        free((char*)block);
564
565    } else {
566        /*-----------------------------------------------------------
567        |   update cache
568        \----------------------------------------------------------*/
569        if (!foundInCache) {
570            /* remove oldest entry and add this block */
571            for (i=1; i < CACHE_SIZE; i++) {
572                bins.blockCache[i-1] = bins.blockCache[i];
573            }
574            bins.blockCache[CACHE_SIZE-1] = block;
575        }
576    }
577    TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/
578}
579