Main Page | Modules | Data Structures | File List | Data Fields | Globals

bmalloc.c File Reference

Detailed Description

Provides memory managment for BeeOS.

Definition in file bmalloc.c.

#include "../include/beeos.h"
#include "../include/bbit.h"
#include "../include/bmalloc.h"
#include "../include/bstring.h"
#include "../include/arch/param.h"
#include <stdarg.h>
#include "../include/bprintf.h"

Include dependency graph for bmalloc.c:

Include dependency graph

Go to the source code of this file.

Defines

#define IN_BMEM   /* "internal" globals, for splint */

Functions

void bmallocinit (void)
 Initialise bmalloc() related data, eg. bheap.

void bfree (char *addr)
 POSIX free() look-alike. Free some previously allocated memory.

char * bmalloc (ushort size, char *pExist)
 POSIX malloc() look-alike. NOT COMPATIBLE. Allocates some memory.

char * bremalloc (ushort size, char *pExist)
 POSIX realloc() look-alike. Non-destructivly resize already alloc'd memory.


Variables

char _end

Define Documentation

#define IN_BMEM   /* "internal" globals, for splint */
 

Definition at line 25 of file bmalloc.c.

Function Documentation

void bfree (  char *  addr  ) 
 

POSIX free() look-alike. Free some previously allocated memory.

Parameters:
addr Address of previously allocated memory.
Warning:
Do not free already freed memory. NULL addr value is not trapped.
Please see notes on thread locking.

Please refer to bmalloc(). Writing to arbitrary locations in the BeeOS bheap WILL kill bfree(), since info about the number of blocks to be freed is stored at (addr-1) and this is used by bfree() to update the BeeOS bheap_bitmap (there is NO boundary checking)

Debugging
Some vaguely useful debug output in HOSTED_BUILD mode can be set via the BMEM_DEBUG define in bmalloc.c.
Thread locking
Waits for global lk_bfree to become false before performing free operation.

Definition at line 105 of file bmalloc.c.

References ALLOC_NUMBLOCKS, bprintf(), SRAM_ADDR2BLOCK, SRAM_BITCLR, sshort, and uchar.

Referenced by bmalloc(), bremalloc(), bubblesort(), and execprep(). 

00107 {   
00121     uchar i = (uchar) SRAM_ADDR2BLOCK(addr);
00122 /*@-nullptrarith@*/
00123     uchar end_block = 0;
00124     
00125 #ifdef BMEM_DEBUG
00126     bprintf(20, "bfr: Free %i blks @%p.\r\n", (sshort)ALLOC_NUMBLOCKS(addr), 
00127         (sshort) addr);
00128 #endif
00129 /*@=nullptrarith@*/
00130     while (lk_bfree);   /* Wait for other thread's bfree() call to finish */
00131     lk_bfree = true;
00132     end_block = (uchar) i + (uchar) ALLOC_NUMBLOCKS(addr);
00133     for (; i < end_block; i++) SRAM_BITCLR(i);
00134     lk_bfree = false;
00135     
00136     return;
00137 }

Here is the call graph for this function:

char * bmalloc (  ushort  size,
char *  pExist
) 
 

POSIX malloc() look-alike. NOT COMPATIBLE. Allocates some memory.

Parameters:
size Allocation request size in bytes.
pExist char pointer to an existing allocation that wants to be resized. For new allocations, pass NULL.
Return values:
pMem Address of allocated memory.
Please see notes on thread locking.

The BeeOS memory allocator. This is a bit different to POSIX malloc() since this function handles resizing existing alloc's too. On failure, bmalloc() returns NULL. pExist should be NULL for new alloc's.

Uses bheap global for the heap to manage. It should be initialised to extern char *_end (set by linker) using bmallocinit() first. bmalloc() uses macros SRAM_BLOCKSIZE and SRAM_NUMBLOCKS for memory calculations. Modify these in bmalloc.h.

bmalloc() uses a simple bitmap to track usage of memory "blocks" of a fixed size.

bmalloc() can cheaply shrink existing alloc's; increasing an alloc can also be cheap if there are enough contiguous free blocks immediately after the current alloc. that can be "absorbed" to meet the requested new size. Otherwise there must exist enough contiguous free blocks elsewhere in the bitmap to allocate a completely new area.

In this case, bmalloc() would return the addr. for the new space, and it would be up to the caller to copy from the old to the new space and free the old space. The caller can of course check for this condition by comparing the existing addr. and the one returned by bmalloc().

realloc feature
The realloc feature of bmalloc() can be disabled by making sure the BREALLOC define is commented out in bmalloc.h. This can save program space.
Debugging
Some vaguely useful debug output in HOSTED_BUILD mode can be set via the BMEM_DEBUG define in bmalloc.h.
Thread locking
Waits for global lk_bmalloc to become false before performing alloc operation.
Warning:
NOT COMPATIBLE with the POSIX malloc() function.

Wait for lk_bmalloc to become false before calling!

Definition at line 150 of file bmalloc.c.

References ALLOC_NUMBLOCKS, bfree(), bprintf(), NULL, SRAM_ADDR2BLOCK, SRAM_BITCHECK, SRAM_BITSET, SRAM_BLOCK2ADDR, SRAM_BLOCKSIZE, SRAM_NUMBLOCKS, sshort, uchar, and ushort.

Referenced by bremalloc(), and bubblesort(). 

00154 {   
00192     char *pMem = NULL;
00193     bool tagged_a_block = false;
00194     bool blockused = false;
00195     /*NB:div. truncated so +1 */
00196     uchar reqrd_blocks = (uchar)(size + 1)/(uchar)SRAM_BLOCKSIZE;
00197     uchar i = 0, tagged_block = 0;
00198     uchar exist_block, exist_blocks;
00199 
00200     while (lk_bmalloc); /* Wait for other thread's bmalloc() call to finish. */
00201     lk_bmalloc = true;
00202     /* NB: reqrd_blocks++ if alloc. accounting byte won't fit with req. size */
00203 /*@-type@*/ /*(char) i++ non-numeric?*/
00204     if (((size + 1) % SRAM_BLOCKSIZE) != 0) reqrd_blocks++;
00205 /*@=type@*/
00206 #ifdef BREALLOC
00207     /* Deal with existing alloc'd address (IE. resize alloc. request) */
00208     if (NULL != pExist) {
00209         exist_blocks = ALLOC_NUMBLOCKS(pExist);
00210         exist_block = (uchar)SRAM_ADDR2BLOCK(pExist);
00211         if (exist_blocks == reqrd_blocks) return pExist;
00212         else if (exist_blocks < reqrd_blocks) {
00213             /* This code allows bmalloc() to reduce a previous alloc */
00214             i = (exist_blocks - reqrd_blocks);
00215             /*@-nullptrarith@*/
00216             pMem = (char *) SRAM_BLOCK2ADDR((int)exist_block + (int)i);
00217             /*@=nullptrarith@*/
00218             *((uchar *)pMem) = i;
00219             bfree(pMem + 1);
00220             ALLOC_NUMBLOCKS(pExist) = reqrd_blocks;
00221             return pExist;
00222         } else { /* This code allows bmalloc() to increase a previous alloc. */
00223             /* Start free block scan just after currently alloc'd blocks */
00224             i = exist_block + exist_blocks;
00225             tagged_block = exist_block;
00226             tagged_a_block = true;
00227         }
00228 #   ifdef BMEM_DEBUG
00229         bprintf(20, "bmal: REA: was %i, need %i.\r\n", (sshort)exist_blocks, 
00230             (sshort)reqrd_blocks);
00231 #   endif
00232     }
00233 #endif
00234     /* Loop until enough contiguous blocks are found to satisfy size required */
00235     while (i < (uchar)SRAM_NUMBLOCKS) {
00236         blockused = SRAM_BITCHECK(i);   /* Consult bitmap: check block i used */
00237         if (tagged_a_block) { /*Below, LHS: +1:include zero diff*/
00238             if ((i - tagged_block + 1) >= (ushort) reqrd_blocks) {
00239                 /* finished searching, enough blocks found*/
00240                 for (i = tagged_block; i < ((uchar) reqrd_blocks + tagged_block); i++)
00241                     SRAM_BITSET(i);     /* Mark bitmap accordingly */
00242 /*@-nullptrarith@*/
00243                 pMem = (char *) SRAM_BLOCK2ADDR(tagged_block);
00244 /*@=nullptrarith@*/
00245                 *pMem = reqrd_blocks;   /* Set accounting byte */
00246                 pMem++;                 /* The next byte is alloc'd heap space*/
00247                 break;
00248             } else if (blockused) tagged_a_block = false;   /*not enough blocks,*/
00249         } else if (!blockused) {        /* ...reset tagged_a_block, start again */
00250             tagged_a_block = true;      /* if block is free (!blockused), and */
00251             tagged_block = i;           /* haven't tagged_a_block yet, tag it */
00252         }
00253         i++;
00254     }
00255 
00256 #ifdef BMEM_DEBUG
00257     bprintf(20, "bmal: ONRET: Tag blk %i (%p) for %i blks.\r\n", 
00258         (sshort)tagged_block, (sshort) pMem, (sshort) reqrd_blocks);
00259     bprintf(20, "bmal: alc sz @ %p: %i blks = %i.\r\n", 
00260         pMem - 1, ALLOC_NUMBLOCKS(pMem), ALLOC_NUMBLOCKS(pMem)*SRAM_BLOCKSIZE);
00261     bprintf(20, "bmal: A2B tst: %i, B2A tst: %p.\r\n", 
00262         (sshort) SRAM_ADDR2BLOCK(pMem), (sshort) SRAM_BLOCK2ADDR(tagged_block));
00263     for (i = 0; (i < 10) && (i < SRAM_NUMBLOCKS); i++) {
00264         /*bsnprintf(tempry, 39, "\tbitmap: %08'B.\r\n", (char) bheap_bitmap[i]);*/
00265         bprintf(20, "\tbmp: 0x%x.\r\n", (sshort) ((char) bheap_bitmap[i]));
00266         /*bputs(tempry);*/
00267     }   /* This code causes badness. */
00268 #endif
00269     lk_bmalloc = false;
00270     
00271     return pMem;
00272 }

Here is the call graph for this function:

void bmallocinit (  void   ) 
 

Initialise bmalloc() related data, eg. bheap.

Warning:
This function MUST be called before any of the bmalloc.c functions are used.

Debugging
Some vaguely useful debug output in HOSTED_BUILD mode can be set via the BMEM_DEBUG define in bmalloc.c.
_end is set by linker; at this point it marks end of ram reserved by compile-time variables etc.

Definition at line 66 of file bmalloc.c.

References _end, bmemset(), bprintf(), SRAM_BLOCKSIZE, SRAM_NUMBLOCKS, sshort, and ushort. 

00069 {   
00073 #ifndef HOSTED_BUILD
00074     bheap = (char *) &_end; 
00076 #else
00077     bheap = malloc((size_t) SRAM_NUMBLOCKS*SRAM_BLOCKSIZE);
00078 #endif
00079     /* About the line below.... not sure _end is supposed to be modified. */
00080     /*_end += (SRAM_NUMBLOCKS*SRAM_BLOCKSIZE);*/ /* update _end to after bheap*/
00081     bmemset(bheap, '\0', (ushort)SRAM_NUMBLOCKS*SRAM_BLOCKSIZE);
00082     bmemset((char *)bheap_bitmap, '\0', (ushort)SRAM_NUMBLOCKS/8);
00083     lk_bfree = false;
00084     lk_bmalloc = false;
00085 #ifdef BMEM_DEBUG
00086     /*@-nullptrarith@*/
00087     bprintf(20, "bminit: bheap %x, frm %p to %p.\r\n", 
00088         (sshort) SRAM_NUMBLOCKS*SRAM_BLOCKSIZE, (sshort) bheap, 
00089         (sshort) bheap + SRAM_NUMBLOCKS*SRAM_BLOCKSIZE);
00090     /*@=nullptrarith@*/
00091 #endif
00092     
00093     return;
00094 }

Here is the call graph for this function:

char * bremalloc (  ushort  size,
char *  pExist
) 
 

POSIX realloc() look-alike. Non-destructivly resize already alloc'd memory.

Parameters:
size Number of bytes in the new requested size.
pExist char pointer to already allocated memory, or NULL (read details).
Return values:
pMem char pointer to the newly resized memory.

A companion to bmalloc(). Read comments for bmalloc() to understand the limitations of using bmalloc() to perform reallocations.

bremalloc() will first call bmalloc() and then check to see if the copy/clear/free process is required.

POSIX calloc() functionality
Zeroes newly acquired memory. As a side-effect, this function can be used to alloc. new memory from scratch (IE. pass NULL for pExist), and have it zeroed.
Thread locking
No thread locking in bremalloc(), since bfree() and bmalloc() are already mulithread-locked.

Definition at line 283 of file bmalloc.c.

References ALLOC_NUMBLOCKS, bfree(), bmalloc(), bmemcpy(), bmemset(), bprintf(), NULL, SRAM_BLOCKSIZE, sshort, uchar, and ushort.

Referenced by create_task(). 

00287 {   
00302     char /*@exposed@*/ *pMem;
00303     uchar oldsize, newsize;
00304 
00305 #   ifdef BMEM_DEBUG
00306     oldsize = 0;    /* ... so that printf() says something sane. */
00307     newsize = 0;
00308 #   endif
00309     
00310     pMem = bmalloc(size, pExist);
00311     if (NULL != pMem) {
00312         /*newsize ..as opposed to requested */
00313         newsize = (uchar) ALLOC_NUMBLOCKS(( (uchar *)pMem ))*SRAM_BLOCKSIZE;
00314         if (NULL != pExist) {
00315             /* oldsize: actual currently alloc'd bytes.. */
00316             oldsize = (uchar) (ALLOC_NUMBLOCKS(( (uchar *)pExist ))*(uchar)SRAM_BLOCKSIZE);
00317             if (newsize > oldsize)
00318                 bmemset(pMem + oldsize, '\0', newsize - oldsize);   /* clear */
00319             if (pMem != pExist) {                           
00320                 bmemcpy(pMem, pExist, oldsize);                 /* copy */
00321             }
00322             bfree(pExist);                                      /* free */
00323         } else {
00324             bmemset(pMem, '\0', newsize);   /* newsize, clear ALL granted bytes */
00325         }
00326     }
00327 
00328 #   ifdef BMEM_DEBUG
00329 /*@-usedef@*/   /* oldsize/newsize may not be defined. Note to self: yes it is */
00330     bprintf(20, "brem: ONRET: oldsz %i, newsz %i, pMem %p, pExist %p.\r\n"
00331         , (sshort) oldsize, (sshort) newsize, (sshort) pMem, (sshort) pExist);
00332 /*@=usedef@*/
00333 #   endif
00334 
00335     return pMem;
00336 /*@-mustmod@*/  /*... splint reckons bheap_bitmap isn't modified */
00337 }

Here is the call graph for this function:

Variable Documentation

char _end
 

Definition at line 43 of file bmalloc.c.

Referenced by bmallocinit().

Generated on Sat Apr 10 17:08:06 2004 for BeeOS by doxygen 1.3.6-20040222