13b6eaa7bSAndrey A. Chernov /* $Header: /src/pub/tcsh/tc.alloc.c,v 3.35 2000/11/11 23:03:38 christos Exp $ */ 2c80476e4SDavid E. O'Brien /* 3c80476e4SDavid E. O'Brien * tc.alloc.c (Caltech) 2/21/82 4c80476e4SDavid E. O'Brien * Chris Kingsley, kingsley@cit-20. 5c80476e4SDavid E. O'Brien * 6c80476e4SDavid E. O'Brien * This is a very fast storage allocator. It allocates blocks of a small 7c80476e4SDavid E. O'Brien * number of different sizes, and keeps free lists of each size. Blocks that 8c80476e4SDavid E. O'Brien * don't exactly fit are passed up to the next larger size. In this 9c80476e4SDavid E. O'Brien * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long. 10c80476e4SDavid E. O'Brien * This is designed for use in a program that uses vast quantities of memory, 11c80476e4SDavid E. O'Brien * but bombs when it runs out. 12c80476e4SDavid E. O'Brien */ 13c80476e4SDavid E. O'Brien /*- 14c80476e4SDavid E. O'Brien * Copyright (c) 1980, 1991 The Regents of the University of California. 15c80476e4SDavid E. O'Brien * All rights reserved. 16c80476e4SDavid E. O'Brien * 17c80476e4SDavid E. O'Brien * Redistribution and use in source and binary forms, with or without 18c80476e4SDavid E. O'Brien * modification, are permitted provided that the following conditions 19c80476e4SDavid E. O'Brien * are met: 20c80476e4SDavid E. O'Brien * 1. Redistributions of source code must retain the above copyright 21c80476e4SDavid E. O'Brien * notice, this list of conditions and the following disclaimer. 22c80476e4SDavid E. O'Brien * 2. Redistributions in binary form must reproduce the above copyright 23c80476e4SDavid E. O'Brien * notice, this list of conditions and the following disclaimer in the 24c80476e4SDavid E. O'Brien * documentation and/or other materials provided with the distribution. 25c80476e4SDavid E. O'Brien * 3. All advertising materials mentioning features or use of this software 26c80476e4SDavid E. O'Brien * must display the following acknowledgement: 27c80476e4SDavid E. O'Brien * This product includes software developed by the University of 28c80476e4SDavid E. O'Brien * California, Berkeley and its contributors. 29c80476e4SDavid E. O'Brien * 4. Neither the name of the University nor the names of its contributors 30c80476e4SDavid E. O'Brien * may be used to endorse or promote products derived from this software 31c80476e4SDavid E. O'Brien * without specific prior written permission. 32c80476e4SDavid E. O'Brien * 33c80476e4SDavid E. O'Brien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 34c80476e4SDavid E. O'Brien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 35c80476e4SDavid E. O'Brien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 36c80476e4SDavid E. O'Brien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 37c80476e4SDavid E. O'Brien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 38c80476e4SDavid E. O'Brien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 39c80476e4SDavid E. O'Brien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 40c80476e4SDavid E. O'Brien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 41c80476e4SDavid E. O'Brien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 42c80476e4SDavid E. O'Brien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 43c80476e4SDavid E. O'Brien * SUCH DAMAGE. 44c80476e4SDavid E. O'Brien */ 45c80476e4SDavid E. O'Brien #include "sh.h" 46c80476e4SDavid E. O'Brien 473b6eaa7bSAndrey A. Chernov RCSID("$Id: tc.alloc.c,v 3.35 2000/11/11 23:03:38 christos Exp $") 48c80476e4SDavid E. O'Brien 49c80476e4SDavid E. O'Brien static char *memtop = NULL; /* PWP: top of current memory */ 50c80476e4SDavid E. O'Brien static char *membot = NULL; /* PWP: bottom of allocatable memory */ 51c80476e4SDavid E. O'Brien 52c80476e4SDavid E. O'Brien int dont_free = 0; 53c80476e4SDavid E. O'Brien 54c80476e4SDavid E. O'Brien #if defined(_VMS_POSIX) || defined(_AMIGA_MEMORY) 55c80476e4SDavid E. O'Brien # define NO_SBRK 56c80476e4SDavid E. O'Brien #endif 57c80476e4SDavid E. O'Brien 583b6eaa7bSAndrey A. Chernov #ifdef WINNT_NATIVE 59c80476e4SDavid E. O'Brien # define malloc fmalloc 60c80476e4SDavid E. O'Brien # define free ffree 61c80476e4SDavid E. O'Brien # define calloc fcalloc 62c80476e4SDavid E. O'Brien # define realloc frealloc 633b6eaa7bSAndrey A. Chernov #endif /* WINNT_NATIVE */ 64c80476e4SDavid E. O'Brien 65c80476e4SDavid E. O'Brien #ifndef SYSMALLOC 66c80476e4SDavid E. O'Brien 67c80476e4SDavid E. O'Brien #undef RCHECK 68c80476e4SDavid E. O'Brien #undef DEBUG 69c80476e4SDavid E. O'Brien 70c80476e4SDavid E. O'Brien #ifdef SX 71c80476e4SDavid E. O'Brien extern void* sbrk(); 72c80476e4SDavid E. O'Brien #endif 73c80476e4SDavid E. O'Brien /* 74c80476e4SDavid E. O'Brien * Lots of os routines are busted and try to free invalid pointers. 75c80476e4SDavid E. O'Brien * Although our free routine is smart enough and it will pick bad 76c80476e4SDavid E. O'Brien * pointers most of the time, in cases where we know we are going to get 77c80476e4SDavid E. O'Brien * a bad pointer, we'd rather leak. 78c80476e4SDavid E. O'Brien */ 79c80476e4SDavid E. O'Brien 80c80476e4SDavid E. O'Brien #ifndef NULL 81c80476e4SDavid E. O'Brien #define NULL 0 82c80476e4SDavid E. O'Brien #endif 83c80476e4SDavid E. O'Brien 84c80476e4SDavid E. O'Brien typedef unsigned char U_char; /* we don't really have signed chars */ 85c80476e4SDavid E. O'Brien typedef unsigned int U_int; 86c80476e4SDavid E. O'Brien typedef unsigned short U_short; 87c80476e4SDavid E. O'Brien typedef unsigned long U_long; 88c80476e4SDavid E. O'Brien 89c80476e4SDavid E. O'Brien 90c80476e4SDavid E. O'Brien /* 91c80476e4SDavid E. O'Brien * The overhead on a block is at least 4 bytes. When free, this space 92c80476e4SDavid E. O'Brien * contains a pointer to the next free block, and the bottom two bits must 93c80476e4SDavid E. O'Brien * be zero. When in use, the first byte is set to MAGIC, and the second 94c80476e4SDavid E. O'Brien * byte is the size index. The remaining bytes are for alignment. 95c80476e4SDavid E. O'Brien * If range checking is enabled and the size of the block fits 96c80476e4SDavid E. O'Brien * in two bytes, then the top two bytes hold the size of the requested block 97c80476e4SDavid E. O'Brien * plus the range checking words, and the header word MINUS ONE. 98c80476e4SDavid E. O'Brien */ 99c80476e4SDavid E. O'Brien 100c80476e4SDavid E. O'Brien 101c80476e4SDavid E. O'Brien #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP) 102c80476e4SDavid E. O'Brien 103c80476e4SDavid E. O'Brien union overhead { 104c80476e4SDavid E. O'Brien union overhead *ov_next; /* when free */ 105c80476e4SDavid E. O'Brien struct { 106c80476e4SDavid E. O'Brien U_char ovu_magic; /* magic number */ 107c80476e4SDavid E. O'Brien U_char ovu_index; /* bucket # */ 108c80476e4SDavid E. O'Brien #ifdef RCHECK 109c80476e4SDavid E. O'Brien U_short ovu_size; /* actual block size */ 110c80476e4SDavid E. O'Brien U_int ovu_rmagic; /* range magic number */ 111c80476e4SDavid E. O'Brien #endif 112c80476e4SDavid E. O'Brien } ovu; 113c80476e4SDavid E. O'Brien #define ov_magic ovu.ovu_magic 114c80476e4SDavid E. O'Brien #define ov_index ovu.ovu_index 115c80476e4SDavid E. O'Brien #define ov_size ovu.ovu_size 116c80476e4SDavid E. O'Brien #define ov_rmagic ovu.ovu_rmagic 117c80476e4SDavid E. O'Brien }; 118c80476e4SDavid E. O'Brien 119c80476e4SDavid E. O'Brien #define MAGIC 0xfd /* magic # on accounting info */ 120c80476e4SDavid E. O'Brien #define RMAGIC 0x55555555 /* magic # on range info */ 121c80476e4SDavid E. O'Brien #ifdef RCHECK 122c80476e4SDavid E. O'Brien #define RSLOP sizeof (U_int) 123c80476e4SDavid E. O'Brien #else 124c80476e4SDavid E. O'Brien #define RSLOP 0 125c80476e4SDavid E. O'Brien #endif 126c80476e4SDavid E. O'Brien 127c80476e4SDavid E. O'Brien 128c80476e4SDavid E. O'Brien #define ROUNDUP 7 129c80476e4SDavid E. O'Brien 130c80476e4SDavid E. O'Brien /* 131c80476e4SDavid E. O'Brien * nextf[i] is the pointer to the next free block of size 2^(i+3). The 132c80476e4SDavid E. O'Brien * smallest allocatable block is 8 bytes. The overhead information 133c80476e4SDavid E. O'Brien * precedes the data area returned to the user. 134c80476e4SDavid E. O'Brien */ 135c80476e4SDavid E. O'Brien #define NBUCKETS ((sizeof(long) << 3) - 3) 136c80476e4SDavid E. O'Brien static union overhead *nextf[NBUCKETS] IZERO_STRUCT; 137c80476e4SDavid E. O'Brien 138c80476e4SDavid E. O'Brien /* 139c80476e4SDavid E. O'Brien * nmalloc[i] is the difference between the number of mallocs and frees 140c80476e4SDavid E. O'Brien * for a given block size. 141c80476e4SDavid E. O'Brien */ 142c80476e4SDavid E. O'Brien static U_int nmalloc[NBUCKETS] IZERO_STRUCT; 143c80476e4SDavid E. O'Brien 144c80476e4SDavid E. O'Brien #ifndef lint 145c80476e4SDavid E. O'Brien static int findbucket __P((union overhead *, int)); 146c80476e4SDavid E. O'Brien static void morecore __P((int)); 147c80476e4SDavid E. O'Brien #endif 148c80476e4SDavid E. O'Brien 149c80476e4SDavid E. O'Brien 150c80476e4SDavid E. O'Brien #ifdef DEBUG 151c80476e4SDavid E. O'Brien # define CHECK(a, str, p) \ 152c80476e4SDavid E. O'Brien if (a) { \ 153c80476e4SDavid E. O'Brien xprintf(str, p); \ 154c80476e4SDavid E. O'Brien xprintf(" (memtop = %lx membot = %lx)\n", memtop, membot); \ 155c80476e4SDavid E. O'Brien abort(); \ 156c80476e4SDavid E. O'Brien } 157c80476e4SDavid E. O'Brien #else 158c80476e4SDavid E. O'Brien # define CHECK(a, str, p) \ 159c80476e4SDavid E. O'Brien if (a) { \ 160c80476e4SDavid E. O'Brien xprintf(str, p); \ 161c80476e4SDavid E. O'Brien xprintf(" (memtop = %lx membot = %lx)\n", memtop, membot); \ 162c80476e4SDavid E. O'Brien return; \ 163c80476e4SDavid E. O'Brien } 164c80476e4SDavid E. O'Brien #endif 165c80476e4SDavid E. O'Brien 166c80476e4SDavid E. O'Brien memalign_t 167c80476e4SDavid E. O'Brien malloc(nbytes) 168c80476e4SDavid E. O'Brien register size_t nbytes; 169c80476e4SDavid E. O'Brien { 170c80476e4SDavid E. O'Brien #ifndef lint 171c80476e4SDavid E. O'Brien register union overhead *p; 172c80476e4SDavid E. O'Brien register int bucket = 0; 173c80476e4SDavid E. O'Brien register unsigned shiftr; 174c80476e4SDavid E. O'Brien 175c80476e4SDavid E. O'Brien /* 176c80476e4SDavid E. O'Brien * Convert amount of memory requested into closest block size stored in 177c80476e4SDavid E. O'Brien * hash buckets which satisfies request. Account for space used per block 178c80476e4SDavid E. O'Brien * for accounting. 179c80476e4SDavid E. O'Brien */ 180c80476e4SDavid E. O'Brien #ifdef SUNOS4 181c80476e4SDavid E. O'Brien /* 182c80476e4SDavid E. O'Brien * SunOS localtime() overwrites the 9th byte on an 8 byte malloc().... 183c80476e4SDavid E. O'Brien * so we get one more... 184c80476e4SDavid E. O'Brien * From Michael Schroeder: This is not true. It depends on the 185c80476e4SDavid E. O'Brien * timezone string. In Europe it can overwrite the 13th byte on a 186c80476e4SDavid E. O'Brien * 12 byte malloc. 187c80476e4SDavid E. O'Brien * So we punt and we always allocate an extra byte. 188c80476e4SDavid E. O'Brien */ 189c80476e4SDavid E. O'Brien nbytes++; 190c80476e4SDavid E. O'Brien #endif 191c80476e4SDavid E. O'Brien 192c80476e4SDavid E. O'Brien nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP); 193c80476e4SDavid E. O'Brien shiftr = (nbytes - 1) >> 2; 194c80476e4SDavid E. O'Brien 195c80476e4SDavid E. O'Brien /* apart from this loop, this is O(1) */ 196c80476e4SDavid E. O'Brien while ((shiftr >>= 1) != 0) 197c80476e4SDavid E. O'Brien bucket++; 198c80476e4SDavid E. O'Brien /* 199c80476e4SDavid E. O'Brien * If nothing in hash bucket right now, request more memory from the 200c80476e4SDavid E. O'Brien * system. 201c80476e4SDavid E. O'Brien */ 202c80476e4SDavid E. O'Brien if (nextf[bucket] == NULL) 203c80476e4SDavid E. O'Brien morecore(bucket); 204c80476e4SDavid E. O'Brien if ((p = (union overhead *) nextf[bucket]) == NULL) { 205c80476e4SDavid E. O'Brien child++; 206c80476e4SDavid E. O'Brien #ifndef DEBUG 207c80476e4SDavid E. O'Brien stderror(ERR_NOMEM); 208c80476e4SDavid E. O'Brien #else 209c80476e4SDavid E. O'Brien showall(NULL, NULL); 210c80476e4SDavid E. O'Brien xprintf(CGETS(19, 1, "nbytes=%d: Out of memory\n"), nbytes); 211c80476e4SDavid E. O'Brien abort(); 212c80476e4SDavid E. O'Brien #endif 213c80476e4SDavid E. O'Brien /* fool lint */ 214c80476e4SDavid E. O'Brien return ((memalign_t) 0); 215c80476e4SDavid E. O'Brien } 216c80476e4SDavid E. O'Brien /* remove from linked list */ 217c80476e4SDavid E. O'Brien nextf[bucket] = nextf[bucket]->ov_next; 218c80476e4SDavid E. O'Brien p->ov_magic = MAGIC; 219c80476e4SDavid E. O'Brien p->ov_index = bucket; 220c80476e4SDavid E. O'Brien nmalloc[bucket]++; 221c80476e4SDavid E. O'Brien #ifdef RCHECK 222c80476e4SDavid E. O'Brien /* 223c80476e4SDavid E. O'Brien * Record allocated size of block and bound space with magic numbers. 224c80476e4SDavid E. O'Brien */ 225c80476e4SDavid E. O'Brien p->ov_size = (p->ov_index <= 13) ? nbytes - 1 : 0; 226c80476e4SDavid E. O'Brien p->ov_rmagic = RMAGIC; 227c80476e4SDavid E. O'Brien *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC; 228c80476e4SDavid E. O'Brien #endif 229c80476e4SDavid E. O'Brien return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead)))); 230c80476e4SDavid E. O'Brien #else 231c80476e4SDavid E. O'Brien if (nbytes) 232c80476e4SDavid E. O'Brien return ((memalign_t) 0); 233c80476e4SDavid E. O'Brien else 234c80476e4SDavid E. O'Brien return ((memalign_t) 0); 235c80476e4SDavid E. O'Brien #endif /* !lint */ 236c80476e4SDavid E. O'Brien } 237c80476e4SDavid E. O'Brien 238c80476e4SDavid E. O'Brien #ifndef lint 239c80476e4SDavid E. O'Brien /* 240c80476e4SDavid E. O'Brien * Allocate more memory to the indicated bucket. 241c80476e4SDavid E. O'Brien */ 242c80476e4SDavid E. O'Brien static void 243c80476e4SDavid E. O'Brien morecore(bucket) 244c80476e4SDavid E. O'Brien register int bucket; 245c80476e4SDavid E. O'Brien { 246c80476e4SDavid E. O'Brien register union overhead *op; 247c80476e4SDavid E. O'Brien register int rnu; /* 2^rnu bytes will be requested */ 248c80476e4SDavid E. O'Brien register int nblks; /* become nblks blocks of the desired size */ 249c80476e4SDavid E. O'Brien register int siz; 250c80476e4SDavid E. O'Brien 251c80476e4SDavid E. O'Brien if (nextf[bucket]) 252c80476e4SDavid E. O'Brien return; 253c80476e4SDavid E. O'Brien /* 254c80476e4SDavid E. O'Brien * Insure memory is allocated on a page boundary. Should make getpageize 255c80476e4SDavid E. O'Brien * call? 256c80476e4SDavid E. O'Brien */ 257c80476e4SDavid E. O'Brien op = (union overhead *) sbrk(0); 258c80476e4SDavid E. O'Brien memtop = (char *) op; 259c80476e4SDavid E. O'Brien if (membot == NULL) 260c80476e4SDavid E. O'Brien membot = memtop; 261c80476e4SDavid E. O'Brien if ((long) op & 0x3ff) { 262c80476e4SDavid E. O'Brien memtop = (char *) sbrk((int) (1024 - ((long) op & 0x3ff))); 263c80476e4SDavid E. O'Brien memtop += (long) (1024 - ((long) op & 0x3ff)); 264c80476e4SDavid E. O'Brien } 265c80476e4SDavid E. O'Brien 266c80476e4SDavid E. O'Brien /* take 2k unless the block is bigger than that */ 267c80476e4SDavid E. O'Brien rnu = (bucket <= 8) ? 11 : bucket + 3; 268c80476e4SDavid E. O'Brien nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ 269c80476e4SDavid E. O'Brien memtop = (char *) sbrk(1 << rnu); /* PWP */ 270c80476e4SDavid E. O'Brien op = (union overhead *) memtop; 271c80476e4SDavid E. O'Brien /* no more room! */ 272c80476e4SDavid E. O'Brien if ((long) op == -1) 273c80476e4SDavid E. O'Brien return; 274c80476e4SDavid E. O'Brien memtop += (long) (1 << rnu); 275c80476e4SDavid E. O'Brien /* 276c80476e4SDavid E. O'Brien * Round up to minimum allocation size boundary and deduct from block count 277c80476e4SDavid E. O'Brien * to reflect. 278c80476e4SDavid E. O'Brien */ 279c80476e4SDavid E. O'Brien if (((U_long) op) & ROUNDUP) { 280c80476e4SDavid E. O'Brien op = (union overhead *) (((U_long) op + (ROUNDUP + 1)) & ~ROUNDUP); 281c80476e4SDavid E. O'Brien nblks--; 282c80476e4SDavid E. O'Brien } 283c80476e4SDavid E. O'Brien /* 284c80476e4SDavid E. O'Brien * Add new memory allocated to that on free list for this hash bucket. 285c80476e4SDavid E. O'Brien */ 286c80476e4SDavid E. O'Brien nextf[bucket] = op; 287c80476e4SDavid E. O'Brien siz = 1 << (bucket + 3); 288c80476e4SDavid E. O'Brien while (--nblks > 0) { 289c80476e4SDavid E. O'Brien op->ov_next = (union overhead *) (((caddr_t) op) + siz); 290c80476e4SDavid E. O'Brien op = (union overhead *) (((caddr_t) op) + siz); 291c80476e4SDavid E. O'Brien } 292c80476e4SDavid E. O'Brien op->ov_next = NULL; 293c80476e4SDavid E. O'Brien } 294c80476e4SDavid E. O'Brien 295c80476e4SDavid E. O'Brien #endif 296c80476e4SDavid E. O'Brien 297c80476e4SDavid E. O'Brien void 298c80476e4SDavid E. O'Brien free(cp) 299c80476e4SDavid E. O'Brien ptr_t cp; 300c80476e4SDavid E. O'Brien { 301c80476e4SDavid E. O'Brien #ifndef lint 302c80476e4SDavid E. O'Brien register int size; 303c80476e4SDavid E. O'Brien register union overhead *op; 304c80476e4SDavid E. O'Brien 305c80476e4SDavid E. O'Brien /* 306c80476e4SDavid E. O'Brien * the don't free flag is there so that we avoid os bugs in routines 307c80476e4SDavid E. O'Brien * that free invalid pointers! 308c80476e4SDavid E. O'Brien */ 309c80476e4SDavid E. O'Brien if (cp == NULL || dont_free) 310c80476e4SDavid E. O'Brien return; 311c80476e4SDavid E. O'Brien CHECK(!memtop || !membot, 312c80476e4SDavid E. O'Brien CGETS(19, 2, "free(%lx) called before any allocations."), cp); 313c80476e4SDavid E. O'Brien CHECK(cp > (ptr_t) memtop, 314c80476e4SDavid E. O'Brien CGETS(19, 3, "free(%lx) above top of memory."), cp); 315c80476e4SDavid E. O'Brien CHECK(cp < (ptr_t) membot, 316c80476e4SDavid E. O'Brien CGETS(19, 4, "free(%lx) below bottom of memory."), cp); 317c80476e4SDavid E. O'Brien op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead))); 318c80476e4SDavid E. O'Brien CHECK(op->ov_magic != MAGIC, 319c80476e4SDavid E. O'Brien CGETS(19, 5, "free(%lx) bad block."), cp); 320c80476e4SDavid E. O'Brien 321c80476e4SDavid E. O'Brien #ifdef RCHECK 322c80476e4SDavid E. O'Brien if (op->ov_index <= 13) 323c80476e4SDavid E. O'Brien CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, 324c80476e4SDavid E. O'Brien CGETS(19, 6, "free(%lx) bad range check."), cp); 325c80476e4SDavid E. O'Brien #endif 326c80476e4SDavid E. O'Brien CHECK(op->ov_index >= NBUCKETS, 327c80476e4SDavid E. O'Brien CGETS(19, 7, "free(%lx) bad block index."), cp); 328c80476e4SDavid E. O'Brien size = op->ov_index; 329c80476e4SDavid E. O'Brien op->ov_next = nextf[size]; 330c80476e4SDavid E. O'Brien nextf[size] = op; 331c80476e4SDavid E. O'Brien 332c80476e4SDavid E. O'Brien nmalloc[size]--; 333c80476e4SDavid E. O'Brien 334c80476e4SDavid E. O'Brien #else 335c80476e4SDavid E. O'Brien if (cp == NULL) 336c80476e4SDavid E. O'Brien return; 337c80476e4SDavid E. O'Brien #endif 338c80476e4SDavid E. O'Brien } 339c80476e4SDavid E. O'Brien 340c80476e4SDavid E. O'Brien memalign_t 341c80476e4SDavid E. O'Brien calloc(i, j) 342c80476e4SDavid E. O'Brien size_t i, j; 343c80476e4SDavid E. O'Brien { 344c80476e4SDavid E. O'Brien #ifndef lint 345c80476e4SDavid E. O'Brien register char *cp, *scp; 346c80476e4SDavid E. O'Brien 347c80476e4SDavid E. O'Brien i *= j; 348c80476e4SDavid E. O'Brien scp = cp = (char *) xmalloc((size_t) i); 349c80476e4SDavid E. O'Brien if (i != 0) 350c80476e4SDavid E. O'Brien do 351c80476e4SDavid E. O'Brien *cp++ = 0; 352c80476e4SDavid E. O'Brien while (--i); 353c80476e4SDavid E. O'Brien 354c80476e4SDavid E. O'Brien return ((memalign_t) scp); 355c80476e4SDavid E. O'Brien #else 356c80476e4SDavid E. O'Brien if (i && j) 357c80476e4SDavid E. O'Brien return ((memalign_t) 0); 358c80476e4SDavid E. O'Brien else 359c80476e4SDavid E. O'Brien return ((memalign_t) 0); 360c80476e4SDavid E. O'Brien #endif 361c80476e4SDavid E. O'Brien } 362c80476e4SDavid E. O'Brien 363c80476e4SDavid E. O'Brien /* 364c80476e4SDavid E. O'Brien * When a program attempts "storage compaction" as mentioned in the 365c80476e4SDavid E. O'Brien * old malloc man page, it realloc's an already freed block. Usually 366c80476e4SDavid E. O'Brien * this is the last block it freed; occasionally it might be farther 367c80476e4SDavid E. O'Brien * back. We have to search all the free lists for the block in order 368c80476e4SDavid E. O'Brien * to determine its bucket: 1st we make one pass thru the lists 369c80476e4SDavid E. O'Brien * checking only the first block in each; if that fails we search 370c80476e4SDavid E. O'Brien * ``realloc_srchlen'' blocks in each list for a match (the variable 371c80476e4SDavid E. O'Brien * is extern so the caller can modify it). If that fails we just copy 372c80476e4SDavid E. O'Brien * however many bytes was given to realloc() and hope it's not huge. 373c80476e4SDavid E. O'Brien */ 374c80476e4SDavid E. O'Brien #ifndef lint 375c80476e4SDavid E. O'Brien /* 4 should be plenty, -1 =>'s whole list */ 376c80476e4SDavid E. O'Brien static int realloc_srchlen = 4; 377c80476e4SDavid E. O'Brien #endif /* lint */ 378c80476e4SDavid E. O'Brien 379c80476e4SDavid E. O'Brien memalign_t 380c80476e4SDavid E. O'Brien realloc(cp, nbytes) 381c80476e4SDavid E. O'Brien ptr_t cp; 382c80476e4SDavid E. O'Brien size_t nbytes; 383c80476e4SDavid E. O'Brien { 384c80476e4SDavid E. O'Brien #ifndef lint 385c80476e4SDavid E. O'Brien register U_int onb; 386c80476e4SDavid E. O'Brien union overhead *op; 387c80476e4SDavid E. O'Brien ptr_t res; 388c80476e4SDavid E. O'Brien register int i; 389c80476e4SDavid E. O'Brien int was_alloced = 0; 390c80476e4SDavid E. O'Brien 391c80476e4SDavid E. O'Brien if (cp == NULL) 392c80476e4SDavid E. O'Brien return (malloc(nbytes)); 393c80476e4SDavid E. O'Brien op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead))); 394c80476e4SDavid E. O'Brien if (op->ov_magic == MAGIC) { 395c80476e4SDavid E. O'Brien was_alloced++; 396c80476e4SDavid E. O'Brien i = op->ov_index; 397c80476e4SDavid E. O'Brien } 398c80476e4SDavid E. O'Brien else 399c80476e4SDavid E. O'Brien /* 400c80476e4SDavid E. O'Brien * Already free, doing "compaction". 401c80476e4SDavid E. O'Brien * 402c80476e4SDavid E. O'Brien * Search for the old block of memory on the free list. First, check the 403c80476e4SDavid E. O'Brien * most common case (last element free'd), then (this failing) the last 404c80476e4SDavid E. O'Brien * ``realloc_srchlen'' items free'd. If all lookups fail, then assume 405c80476e4SDavid E. O'Brien * the size of the memory block being realloc'd is the smallest 406c80476e4SDavid E. O'Brien * possible. 407c80476e4SDavid E. O'Brien */ 408c80476e4SDavid E. O'Brien if ((i = findbucket(op, 1)) < 0 && 409c80476e4SDavid E. O'Brien (i = findbucket(op, realloc_srchlen)) < 0) 410c80476e4SDavid E. O'Brien i = 0; 411c80476e4SDavid E. O'Brien 412c80476e4SDavid E. O'Brien onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP); 413c80476e4SDavid E. O'Brien 414c80476e4SDavid E. O'Brien /* avoid the copy if same size block */ 415c80476e4SDavid E. O'Brien if (was_alloced && (onb <= (U_int) (1 << (i + 3))) && 416c80476e4SDavid E. O'Brien (onb > (U_int) (1 << (i + 2)))) { 417c80476e4SDavid E. O'Brien #ifdef RCHECK 418c80476e4SDavid E. O'Brien /* JMR: formerly this wasn't updated ! */ 419c80476e4SDavid E. O'Brien nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead))+nbytes+RSLOP); 420c80476e4SDavid E. O'Brien *((U_int *) (((caddr_t) op) + nbytes - RSLOP)) = RMAGIC; 421c80476e4SDavid E. O'Brien op->ov_rmagic = RMAGIC; 422c80476e4SDavid E. O'Brien op->ov_size = (op->ov_index <= 13) ? nbytes - 1 : 0; 423c80476e4SDavid E. O'Brien #endif 424c80476e4SDavid E. O'Brien return ((memalign_t) cp); 425c80476e4SDavid E. O'Brien } 426c80476e4SDavid E. O'Brien if ((res = malloc(nbytes)) == NULL) 427c80476e4SDavid E. O'Brien return ((memalign_t) NULL); 428c80476e4SDavid E. O'Brien if (cp != res) { /* common optimization */ 429c80476e4SDavid E. O'Brien /* 430c80476e4SDavid E. O'Brien * christos: this used to copy nbytes! It should copy the 431c80476e4SDavid E. O'Brien * smaller of the old and new size 432c80476e4SDavid E. O'Brien */ 433c80476e4SDavid E. O'Brien onb = (1 << (i + 3)) - MEMALIGN(sizeof(union overhead)) - RSLOP; 434c80476e4SDavid E. O'Brien (void) memmove((ptr_t) res, (ptr_t) cp, 435c80476e4SDavid E. O'Brien (size_t) (onb < nbytes ? onb : nbytes)); 436c80476e4SDavid E. O'Brien } 437c80476e4SDavid E. O'Brien if (was_alloced) 438c80476e4SDavid E. O'Brien free(cp); 439c80476e4SDavid E. O'Brien return ((memalign_t) res); 440c80476e4SDavid E. O'Brien #else 441c80476e4SDavid E. O'Brien if (cp && nbytes) 442c80476e4SDavid E. O'Brien return ((memalign_t) 0); 443c80476e4SDavid E. O'Brien else 444c80476e4SDavid E. O'Brien return ((memalign_t) 0); 445c80476e4SDavid E. O'Brien #endif /* !lint */ 446c80476e4SDavid E. O'Brien } 447c80476e4SDavid E. O'Brien 448c80476e4SDavid E. O'Brien 449c80476e4SDavid E. O'Brien 450c80476e4SDavid E. O'Brien #ifndef lint 451c80476e4SDavid E. O'Brien /* 452c80476e4SDavid E. O'Brien * Search ``srchlen'' elements of each free list for a block whose 453c80476e4SDavid E. O'Brien * header starts at ``freep''. If srchlen is -1 search the whole list. 454c80476e4SDavid E. O'Brien * Return bucket number, or -1 if not found. 455c80476e4SDavid E. O'Brien */ 456c80476e4SDavid E. O'Brien static int 457c80476e4SDavid E. O'Brien findbucket(freep, srchlen) 458c80476e4SDavid E. O'Brien union overhead *freep; 459c80476e4SDavid E. O'Brien int srchlen; 460c80476e4SDavid E. O'Brien { 461c80476e4SDavid E. O'Brien register union overhead *p; 462c80476e4SDavid E. O'Brien register int i, j; 463c80476e4SDavid E. O'Brien 464c80476e4SDavid E. O'Brien for (i = 0; i < NBUCKETS; i++) { 465c80476e4SDavid E. O'Brien j = 0; 466c80476e4SDavid E. O'Brien for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 467c80476e4SDavid E. O'Brien if (p == freep) 468c80476e4SDavid E. O'Brien return (i); 469c80476e4SDavid E. O'Brien j++; 470c80476e4SDavid E. O'Brien } 471c80476e4SDavid E. O'Brien } 472c80476e4SDavid E. O'Brien return (-1); 473c80476e4SDavid E. O'Brien } 474c80476e4SDavid E. O'Brien 475c80476e4SDavid E. O'Brien #endif 476c80476e4SDavid E. O'Brien 477c80476e4SDavid E. O'Brien 478c80476e4SDavid E. O'Brien #else /* SYSMALLOC */ 479c80476e4SDavid E. O'Brien 480c80476e4SDavid E. O'Brien /** 481c80476e4SDavid E. O'Brien ** ``Protected versions'' of malloc, realloc, calloc, and free 482c80476e4SDavid E. O'Brien ** 483c80476e4SDavid E. O'Brien ** On many systems: 484c80476e4SDavid E. O'Brien ** 485c80476e4SDavid E. O'Brien ** 1. malloc(0) is bad 486c80476e4SDavid E. O'Brien ** 2. free(0) is bad 487c80476e4SDavid E. O'Brien ** 3. realloc(0, n) is bad 488c80476e4SDavid E. O'Brien ** 4. realloc(n, 0) is bad 489c80476e4SDavid E. O'Brien ** 490c80476e4SDavid E. O'Brien ** Also we call our error routine if we run out of memory. 491c80476e4SDavid E. O'Brien **/ 492c80476e4SDavid E. O'Brien memalign_t 493c80476e4SDavid E. O'Brien smalloc(n) 494c80476e4SDavid E. O'Brien size_t n; 495c80476e4SDavid E. O'Brien { 496c80476e4SDavid E. O'Brien ptr_t ptr; 497c80476e4SDavid E. O'Brien 498c80476e4SDavid E. O'Brien n = n ? n : 1; 499c80476e4SDavid E. O'Brien 500c80476e4SDavid E. O'Brien #ifndef NO_SBRK 501c80476e4SDavid E. O'Brien if (membot == NULL) 502c80476e4SDavid E. O'Brien membot = (char*) sbrk(0); 503c80476e4SDavid E. O'Brien #endif /* !NO_SBRK */ 504c80476e4SDavid E. O'Brien 505c80476e4SDavid E. O'Brien if ((ptr = malloc(n)) == (ptr_t) 0) { 506c80476e4SDavid E. O'Brien child++; 507c80476e4SDavid E. O'Brien stderror(ERR_NOMEM); 508c80476e4SDavid E. O'Brien } 509c80476e4SDavid E. O'Brien #ifdef NO_SBRK 510c80476e4SDavid E. O'Brien if (memtop < ((char *) ptr) + n) 511c80476e4SDavid E. O'Brien memtop = ((char *) ptr) + n; 512c80476e4SDavid E. O'Brien if (membot == NULL) 513c80476e4SDavid E. O'Brien membot = (char*) ptr; 514c80476e4SDavid E. O'Brien #endif /* NO_SBRK */ 515c80476e4SDavid E. O'Brien return ((memalign_t) ptr); 516c80476e4SDavid E. O'Brien } 517c80476e4SDavid E. O'Brien 518c80476e4SDavid E. O'Brien memalign_t 519c80476e4SDavid E. O'Brien srealloc(p, n) 520c80476e4SDavid E. O'Brien ptr_t p; 521c80476e4SDavid E. O'Brien size_t n; 522c80476e4SDavid E. O'Brien { 523c80476e4SDavid E. O'Brien ptr_t ptr; 524c80476e4SDavid E. O'Brien 525c80476e4SDavid E. O'Brien n = n ? n : 1; 526c80476e4SDavid E. O'Brien 527c80476e4SDavid E. O'Brien #ifndef NO_SBRK 528c80476e4SDavid E. O'Brien if (membot == NULL) 529c80476e4SDavid E. O'Brien membot = (char*) sbrk(0); 530c80476e4SDavid E. O'Brien #endif /* NO_SBRK */ 531c80476e4SDavid E. O'Brien 532c80476e4SDavid E. O'Brien if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) { 533c80476e4SDavid E. O'Brien child++; 534c80476e4SDavid E. O'Brien stderror(ERR_NOMEM); 535c80476e4SDavid E. O'Brien } 536c80476e4SDavid E. O'Brien #ifdef NO_SBRK 537c80476e4SDavid E. O'Brien if (memtop < ((char *) ptr) + n) 538c80476e4SDavid E. O'Brien memtop = ((char *) ptr) + n; 539c80476e4SDavid E. O'Brien if (membot == NULL) 540c80476e4SDavid E. O'Brien membot = (char*) ptr; 541c80476e4SDavid E. O'Brien #endif /* NO_SBRK */ 542c80476e4SDavid E. O'Brien return ((memalign_t) ptr); 543c80476e4SDavid E. O'Brien } 544c80476e4SDavid E. O'Brien 545c80476e4SDavid E. O'Brien memalign_t 546c80476e4SDavid E. O'Brien scalloc(s, n) 547c80476e4SDavid E. O'Brien size_t s, n; 548c80476e4SDavid E. O'Brien { 549c80476e4SDavid E. O'Brien char *sptr; 550c80476e4SDavid E. O'Brien ptr_t ptr; 551c80476e4SDavid E. O'Brien 552c80476e4SDavid E. O'Brien n *= s; 553c80476e4SDavid E. O'Brien n = n ? n : 1; 554c80476e4SDavid E. O'Brien 555c80476e4SDavid E. O'Brien #ifndef NO_SBRK 556c80476e4SDavid E. O'Brien if (membot == NULL) 557c80476e4SDavid E. O'Brien membot = (char*) sbrk(0); 558c80476e4SDavid E. O'Brien #endif /* NO_SBRK */ 559c80476e4SDavid E. O'Brien 560c80476e4SDavid E. O'Brien if ((ptr = malloc(n)) == (ptr_t) 0) { 561c80476e4SDavid E. O'Brien child++; 562c80476e4SDavid E. O'Brien stderror(ERR_NOMEM); 563c80476e4SDavid E. O'Brien } 564c80476e4SDavid E. O'Brien 565c80476e4SDavid E. O'Brien sptr = (char *) ptr; 566c80476e4SDavid E. O'Brien if (n != 0) 567c80476e4SDavid E. O'Brien do 568c80476e4SDavid E. O'Brien *sptr++ = 0; 569c80476e4SDavid E. O'Brien while (--n); 570c80476e4SDavid E. O'Brien 571c80476e4SDavid E. O'Brien #ifdef NO_SBRK 572c80476e4SDavid E. O'Brien if (memtop < ((char *) ptr) + n) 573c80476e4SDavid E. O'Brien memtop = ((char *) ptr) + n; 574c80476e4SDavid E. O'Brien if (membot == NULL) 575c80476e4SDavid E. O'Brien membot = (char*) ptr; 576c80476e4SDavid E. O'Brien #endif /* NO_SBRK */ 577c80476e4SDavid E. O'Brien 578c80476e4SDavid E. O'Brien return ((memalign_t) ptr); 579c80476e4SDavid E. O'Brien } 580c80476e4SDavid E. O'Brien 581c80476e4SDavid E. O'Brien void 582c80476e4SDavid E. O'Brien sfree(p) 583c80476e4SDavid E. O'Brien ptr_t p; 584c80476e4SDavid E. O'Brien { 585c80476e4SDavid E. O'Brien if (p && !dont_free) 586c80476e4SDavid E. O'Brien free(p); 587c80476e4SDavid E. O'Brien } 588c80476e4SDavid E. O'Brien 589c80476e4SDavid E. O'Brien #endif /* SYSMALLOC */ 590c80476e4SDavid E. O'Brien 591c80476e4SDavid E. O'Brien /* 592c80476e4SDavid E. O'Brien * mstats - print out statistics about malloc 593c80476e4SDavid E. O'Brien * 594c80476e4SDavid E. O'Brien * Prints two lines of numbers, one showing the length of the free list 595c80476e4SDavid E. O'Brien * for each size category, the second showing the number of mallocs - 596c80476e4SDavid E. O'Brien * frees for each size category. 597c80476e4SDavid E. O'Brien */ 598c80476e4SDavid E. O'Brien /*ARGSUSED*/ 599c80476e4SDavid E. O'Brien void 600c80476e4SDavid E. O'Brien showall(v, c) 601c80476e4SDavid E. O'Brien Char **v; 602c80476e4SDavid E. O'Brien struct command *c; 603c80476e4SDavid E. O'Brien { 604c80476e4SDavid E. O'Brien #ifndef SYSMALLOC 605c80476e4SDavid E. O'Brien register int i, j; 606c80476e4SDavid E. O'Brien register union overhead *p; 607c80476e4SDavid E. O'Brien int totfree = 0, totused = 0; 608c80476e4SDavid E. O'Brien 609c80476e4SDavid E. O'Brien xprintf(CGETS(19, 8, "%s current memory allocation:\nfree:\t"), progname); 610c80476e4SDavid E. O'Brien for (i = 0; i < NBUCKETS; i++) { 611c80476e4SDavid E. O'Brien for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 612c80476e4SDavid E. O'Brien continue; 613c80476e4SDavid E. O'Brien xprintf(" %4d", j); 614c80476e4SDavid E. O'Brien totfree += j * (1 << (i + 3)); 615c80476e4SDavid E. O'Brien } 616c80476e4SDavid E. O'Brien xprintf(CGETS(19, 9, "\nused:\t")); 617c80476e4SDavid E. O'Brien for (i = 0; i < NBUCKETS; i++) { 618c80476e4SDavid E. O'Brien xprintf(" %4u", nmalloc[i]); 619c80476e4SDavid E. O'Brien totused += nmalloc[i] * (1 << (i + 3)); 620c80476e4SDavid E. O'Brien } 621c80476e4SDavid E. O'Brien xprintf(CGETS(19, 10, "\n\tTotal in use: %d, total free: %d\n"), 622c80476e4SDavid E. O'Brien totused, totfree); 623c80476e4SDavid E. O'Brien xprintf(CGETS(19, 11, 624c80476e4SDavid E. O'Brien "\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n"), 625c80476e4SDavid E. O'Brien (unsigned long) membot, (unsigned long) memtop, 626c80476e4SDavid E. O'Brien (unsigned long) sbrk(0)); 627c80476e4SDavid E. O'Brien #else 628c80476e4SDavid E. O'Brien #ifndef NO_SBRK 629c80476e4SDavid E. O'Brien memtop = (char *) sbrk(0); 630c80476e4SDavid E. O'Brien #endif /* !NO_SBRK */ 631c80476e4SDavid E. O'Brien xprintf(CGETS(19, 12, "Allocated memory from 0x%lx to 0x%lx (%ld).\n"), 632c80476e4SDavid E. O'Brien (unsigned long) membot, (unsigned long) memtop, 633c80476e4SDavid E. O'Brien (unsigned long) (memtop - membot)); 634c80476e4SDavid E. O'Brien #endif /* SYSMALLOC */ 635c80476e4SDavid E. O'Brien USE(c); 636c80476e4SDavid E. O'Brien USE(v); 637c80476e4SDavid E. O'Brien } 638