1100364Smarkm/* $NetBSD: mem1.c,v 1.7 2002/01/31 19:36:54 tv Exp $ */ 212099Sjoerg 312099Sjoerg/* 412099Sjoerg * Copyright (c) 1994, 1995 Jochen Pohl 512099Sjoerg * All Rights Reserved. 612099Sjoerg * 712099Sjoerg * Redistribution and use in source and binary forms, with or without 812099Sjoerg * modification, are permitted provided that the following conditions 912099Sjoerg * are met: 1012099Sjoerg * 1. Redistributions of source code must retain the above copyright 1112099Sjoerg * notice, this list of conditions and the following disclaimer. 1212099Sjoerg * 2. Redistributions in binary form must reproduce the above copyright 1312099Sjoerg * notice, this list of conditions and the following disclaimer in the 1412099Sjoerg * documentation and/or other materials provided with the distribution. 1512099Sjoerg * 3. All advertising materials mentioning features or use of this software 1612099Sjoerg * must display the following acknowledgement: 1712099Sjoerg * This product includes software developed by Jochen Pohl for 1812099Sjoerg * The NetBSD Project. 1912099Sjoerg * 4. The name of the author may not be used to endorse or promote products 2012099Sjoerg * derived from this software without specific prior written permission. 2112099Sjoerg * 2212099Sjoerg * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2312099Sjoerg * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2412099Sjoerg * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2512099Sjoerg * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2612099Sjoerg * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2712099Sjoerg * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2812099Sjoerg * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2912099Sjoerg * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3012099Sjoerg * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3112099Sjoerg * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3212099Sjoerg */ 3312099Sjoerg 3491592Smarkm#include <sys/cdefs.h> 3591592Smarkm#if defined(__RCSID) && !defined(lint) 36100364Smarkm__RCSID("$NetBSD: mem1.c,v 1.7 2002/01/31 19:36:54 tv Exp $"); 3712099Sjoerg#endif 3891592Smarkm__FBSDID("$FreeBSD$"); 3912099Sjoerg 4012099Sjoerg#include <sys/types.h> 4112099Sjoerg#include <sys/mman.h> 4212099Sjoerg#include <sys/param.h> 43148723Sstefanf#include <err.h> 4412099Sjoerg#include <stdlib.h> 4512099Sjoerg#include <string.h> 4612099Sjoerg#include <unistd.h> 4712099Sjoerg 4812099Sjoerg#include "lint1.h" 4912099Sjoerg 5012099Sjoerg/* 5112099Sjoerg * Filenames allocated by fnalloc() and fnnalloc() are shared. 5212099Sjoerg */ 5312099Sjoergtypedef struct fn { 5412099Sjoerg char *fn_name; 5512099Sjoerg size_t fn_len; 5612099Sjoerg int fn_id; 5712099Sjoerg struct fn *fn_nxt; 5812099Sjoerg} fn_t; 5912099Sjoerg 6012099Sjoergstatic fn_t *fnames; 6112099Sjoerg 6291592Smarkmstatic fn_t *srchfn(const char *, size_t); 6312099Sjoerg 6412099Sjoerg/* 6512099Sjoerg * Look for a Filename of length l. 6612099Sjoerg */ 6712099Sjoergstatic fn_t * 6891592Smarkmsrchfn(const char *s, size_t len) 6912099Sjoerg{ 7012099Sjoerg fn_t *fn; 7112099Sjoerg 7212099Sjoerg for (fn = fnames; fn != NULL; fn = fn->fn_nxt) { 7312099Sjoerg if (fn->fn_len == len && memcmp(fn->fn_name, s, len) == 0) 7412099Sjoerg break; 7512099Sjoerg } 7612099Sjoerg return (fn); 7712099Sjoerg} 7812099Sjoerg 7912099Sjoerg/* 8012099Sjoerg * Return a shared string for filename s. 8112099Sjoerg */ 8212099Sjoergconst char * 8391592Smarkmfnalloc(const char *s) 8412099Sjoerg{ 8591592Smarkm 8612099Sjoerg return (s != NULL ? fnnalloc(s, strlen(s)) : NULL); 8712099Sjoerg} 8812099Sjoerg 8912099Sjoergconst char * 9091592Smarkmfnnalloc(const char *s, size_t len) 9112099Sjoerg{ 9212099Sjoerg fn_t *fn; 9312099Sjoerg 9412099Sjoerg static int nxt_id = 0; 9512099Sjoerg 9612099Sjoerg if (s == NULL) 9712099Sjoerg return (NULL); 9812099Sjoerg 9912099Sjoerg if ((fn = srchfn(s, len)) == NULL) { 10080284Sobrien if ((fn = malloc(sizeof (fn_t))) == NULL) 10180284Sobrien nomem(); 10212099Sjoerg /* Do not used strdup() because string is not NUL-terminated.*/ 10380284Sobrien if ((fn->fn_name = malloc(len + 1)) == NULL) 10480284Sobrien nomem(); 10512099Sjoerg (void)memcpy(fn->fn_name, s, len); 10612099Sjoerg fn->fn_name[len] = '\0'; 10712099Sjoerg fn->fn_len = len; 10812099Sjoerg fn->fn_id = nxt_id++; 10912099Sjoerg fn->fn_nxt = fnames; 11012099Sjoerg fnames = fn; 11112099Sjoerg /* Write id of this filename to the output file. */ 11212099Sjoerg outclr(); 11312099Sjoerg outint(fn->fn_id); 11412099Sjoerg outchar('s'); 11512099Sjoerg outstrg(fn->fn_name); 11612099Sjoerg } 11712099Sjoerg return (fn->fn_name); 11812099Sjoerg} 11912099Sjoerg 12012099Sjoerg/* 12112099Sjoerg * Get id of a filename. 12212099Sjoerg */ 12312099Sjoergint 12491592Smarkmgetfnid(const char *s) 12512099Sjoerg{ 12612099Sjoerg fn_t *fn; 12712099Sjoerg 12812099Sjoerg if (s == NULL || (fn = srchfn(s, strlen(s))) == NULL) 12912099Sjoerg return (-1); 13012099Sjoerg return (fn->fn_id); 13112099Sjoerg} 13212099Sjoerg 13312099Sjoerg/* 13412099Sjoerg * Memory for declarations and other things which must be available 13512099Sjoerg * until the end of a block (or the end of the translation unit) 136228992Suqs * are associated with the level (mblklev) of the block (or with 0). 13712099Sjoerg * Because these memory is allocated in large blocks associated with 13812099Sjoerg * a given level it can be freed easily at the end of a block. 13912099Sjoerg */ 14012099Sjoerg#define ML_INC ((size_t)32) /* Increment for length of *mblks */ 14112099Sjoerg 14212099Sjoergtypedef struct mbl { 14312099Sjoerg void *blk; /* beginning of memory block */ 14412099Sjoerg void *ffree; /* first free byte */ 14512099Sjoerg size_t nfree; /* # of free bytes */ 14612099Sjoerg size_t size; /* total size of memory block */ 14712099Sjoerg struct mbl *nxt; /* next block */ 14812099Sjoerg} mbl_t; 14912099Sjoerg 15012099Sjoerg/* 15112099Sjoerg * Array of pointers to lists of memory blocks. mblklev is used as 15212099Sjoerg * index into this array. 15312099Sjoerg */ 15412099Sjoergstatic mbl_t **mblks; 15512099Sjoerg 15612099Sjoerg/* number of elements in *mblks */ 15712099Sjoergstatic size_t nmblks; 15812099Sjoerg 15912099Sjoerg/* free list for memory blocks */ 16012099Sjoergstatic mbl_t *frmblks; 16112099Sjoerg 16212099Sjoerg/* length of new allocated memory blocks */ 16312099Sjoergstatic size_t mblklen; 16412099Sjoerg 16591592Smarkmstatic void *xgetblk(mbl_t **, size_t); 16691592Smarkmstatic void xfreeblk(mbl_t **); 16791592Smarkmstatic mbl_t *xnewblk(void); 16812099Sjoerg 16912099Sjoergstatic mbl_t * 17091592Smarkmxnewblk(void) 17112099Sjoerg{ 17212099Sjoerg mbl_t *mb; 17312099Sjoerg int prot, flags; 17412099Sjoerg 17580284Sobrien if ((mb = malloc(sizeof (mbl_t))) == NULL) 17680284Sobrien nomem(); 17712099Sjoerg 17812099Sjoerg /* use mmap instead of malloc to avoid malloc's size overhead */ 17912099Sjoerg 18012099Sjoerg prot = PROT_READ | PROT_WRITE; 18112099Sjoerg flags = MAP_ANON | MAP_PRIVATE; 18212099Sjoerg mb->blk = mmap(NULL, mblklen, prot, flags, -1, (off_t)0); 18321786Salex if (mb->blk == (void *)MAP_FAILED) 18412099Sjoerg err(1, "can't map memory"); 18512099Sjoerg 18612099Sjoerg mb->size = mblklen; 18712099Sjoerg 18812099Sjoerg return (mb); 18912099Sjoerg} 19012099Sjoerg 19112099Sjoerg/* 19212099Sjoerg * Allocate new memory. If the first block of the list has not enough 19312099Sjoerg * free space, or there is no first block, get a new block. The new 19412099Sjoerg * block is taken from the free list or, if there is no block on the 19512099Sjoerg * free list, is allocated using xnewblk(). If a new block is allocated 19612099Sjoerg * it is initialized with zero. Blocks taken from the free list are 19712099Sjoerg * zero'd in xfreeblk(). 19812099Sjoerg */ 19912099Sjoergstatic void * 20091592Smarkmxgetblk(mbl_t **mbp, size_t s) 20112099Sjoerg{ 20212099Sjoerg mbl_t *mb; 20312099Sjoerg void *p; 204100364Smarkm size_t t = 0; 20512099Sjoerg 206206424Srdivacky s = LINT_ALIGN(s); 20712099Sjoerg if ((mb = *mbp) == NULL || mb->nfree < s) { 20812099Sjoerg if ((mb = frmblks) == NULL) { 209100364Smarkm if (s > mblklen) { 210100364Smarkm t = mblklen; 211100364Smarkm mblklen = s; 212100364Smarkm } 21312099Sjoerg mb = xnewblk(); 214100364Smarkm if (t) 215100364Smarkm mblklen = t; 21612099Sjoerg (void)memset(mb->blk, 0, mb->size); 21712099Sjoerg } else { 21812099Sjoerg frmblks = mb->nxt; 21912099Sjoerg } 22012099Sjoerg mb->ffree = mb->blk; 221210088Semaste mb->nfree = mb->size; 22212099Sjoerg mb->nxt = *mbp; 22312099Sjoerg *mbp = mb; 22412099Sjoerg } 22512099Sjoerg p = mb->ffree; 22612099Sjoerg mb->ffree = (char *)mb->ffree + s; 22712099Sjoerg mb->nfree -= s; 22812099Sjoerg return (p); 22912099Sjoerg} 23012099Sjoerg 23112099Sjoerg/* 23212099Sjoerg * Move all blocks from list *fmbp to free list. For each block, set all 23312099Sjoerg * used memory to zero. 23412099Sjoerg */ 23512099Sjoergstatic void 23691592Smarkmxfreeblk(mbl_t **fmbp) 23712099Sjoerg{ 23812099Sjoerg mbl_t *mb; 23912099Sjoerg 24012099Sjoerg while ((mb = *fmbp) != NULL) { 24112099Sjoerg *fmbp = mb->nxt; 24212099Sjoerg mb->nxt = frmblks; 24312099Sjoerg frmblks = mb; 24412099Sjoerg (void)memset(mb->blk, 0, mb->size - mb->nfree); 24512099Sjoerg } 24612099Sjoerg} 24712099Sjoerg 24812099Sjoergvoid 24991592Smarkminitmem(void) 25012099Sjoerg{ 25112099Sjoerg int pgsz; 25212099Sjoerg 25312099Sjoerg pgsz = getpagesize(); 25412099Sjoerg mblklen = ((MBLKSIZ + pgsz - 1) / pgsz) * pgsz; 25512099Sjoerg 25680284Sobrien if ((mblks = calloc(nmblks = ML_INC, sizeof (mbl_t *))) == NULL) 25780284Sobrien nomem(); 25812099Sjoerg} 25912099Sjoerg 26091592Smarkm 26112099Sjoerg/* 26212099Sjoerg * Allocate memory associated with level l. 26312099Sjoerg */ 26412099Sjoergvoid * 26591592Smarkmgetlblk(int l, size_t s) 26612099Sjoerg{ 26791592Smarkm 26812099Sjoerg while (l >= nmblks) { 26980284Sobrien if ((mblks = realloc(mblks, (nmblks + ML_INC) * 27080284Sobrien sizeof (mbl_t *))) == NULL) 27180284Sobrien nomem(); 27212099Sjoerg (void)memset(&mblks[nmblks], 0, ML_INC * sizeof (mbl_t *)); 27312099Sjoerg nmblks += ML_INC; 27412099Sjoerg } 27512099Sjoerg return (xgetblk(&mblks[l], s)); 27612099Sjoerg} 27712099Sjoerg 27812099Sjoergvoid * 27991592Smarkmgetblk(size_t s) 28012099Sjoerg{ 28191592Smarkm 28212099Sjoerg return (getlblk(mblklev, s)); 28312099Sjoerg} 28412099Sjoerg 28512099Sjoerg/* 28612099Sjoerg * Free all memory associated with level l. 28712099Sjoerg */ 28812099Sjoergvoid 28991592Smarkmfreelblk(int l) 29012099Sjoerg{ 29191592Smarkm 29212099Sjoerg xfreeblk(&mblks[l]); 29312099Sjoerg} 29412099Sjoerg 29512099Sjoergvoid 29691592Smarkmfreeblk(void) 29712099Sjoerg{ 29891592Smarkm 29912099Sjoerg freelblk(mblklev); 30012099Sjoerg} 30112099Sjoerg 30212099Sjoerg/* 30312099Sjoerg * tgetblk() returns memory which is associated with the current 30412099Sjoerg * expression. 30512099Sjoerg */ 30612099Sjoergstatic mbl_t *tmblk; 30712099Sjoerg 30812099Sjoergvoid * 30991592Smarkmtgetblk(size_t s) 31012099Sjoerg{ 31191592Smarkm 31212099Sjoerg return (xgetblk(&tmblk, s)); 31312099Sjoerg} 31412099Sjoerg 31512099Sjoerg/* 31612099Sjoerg * Get memory for a new tree node. 31712099Sjoerg */ 31812099Sjoergtnode_t * 31991592Smarkmgetnode(void) 32012099Sjoerg{ 32191592Smarkm 32212099Sjoerg return (tgetblk(sizeof (tnode_t))); 32312099Sjoerg} 32412099Sjoerg 32512099Sjoerg/* 32691592Smarkm * Free all memory which is allocated by the current expression. 32712099Sjoerg */ 32812099Sjoergvoid 32991592Smarkmtfreeblk(void) 33012099Sjoerg{ 33191592Smarkm 33212099Sjoerg xfreeblk(&tmblk); 33312099Sjoerg} 33412099Sjoerg 33512099Sjoerg/* 33612099Sjoerg * Save the memory which is used by the current expression. This memory 33712099Sjoerg * is not freed by the next tfreeblk() call. The pointer returned can be 33812099Sjoerg * used to restore the memory. 33912099Sjoerg */ 34012099Sjoergmbl_t * 34191592Smarkmtsave(void) 34212099Sjoerg{ 34312099Sjoerg mbl_t *tmem; 34412099Sjoerg 34512099Sjoerg tmem = tmblk; 34612099Sjoerg tmblk = NULL; 34712099Sjoerg return (tmem); 34812099Sjoerg} 34912099Sjoerg 35012099Sjoerg/* 35112099Sjoerg * Free all memory used for the current expression and the memory used 35212099Sjoerg * be a previous expression and saved by tsave(). The next call to 35312099Sjoerg * tfreeblk() frees the restored memory. 35412099Sjoerg */ 35512099Sjoergvoid 35691592Smarkmtrestor(mbl_t *tmem) 35712099Sjoerg{ 35891592Smarkm 35912099Sjoerg tfreeblk(); 36012099Sjoerg if (tmblk != NULL) { 36112099Sjoerg free(tmblk->blk); 36212099Sjoerg free(tmblk); 36312099Sjoerg } 36412099Sjoerg tmblk = tmem; 36512099Sjoerg} 366