1 /* 2 * Copyright (c) 1987, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)kern_malloc.c 7.34 (Berkeley) 10/09/92 8 */ 9 10 #include "param.h" 11 #include "proc.h" 12 #include "map.h" 13 #include "kernel.h" 14 #include "malloc.h" 15 #include "vm/vm.h" 16 #include "vm/vm_kern.h" 17 18 struct kmembuckets bucket[MINBUCKET + 16]; 19 struct kmemstats kmemstats[M_LAST]; 20 struct kmemusage *kmemusage; 21 char *kmembase, *kmemlimit; 22 char *memname[] = INITKMEMNAMES; 23 24 #ifdef DIAGNOSTIC 25 /* 26 * This structure provides a set of masks to catch unaligned frees. 27 */ 28 long addrmask[] = { 0, 29 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 30 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 31 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 32 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 33 }; 34 35 /* 36 * The WEIRD_ADDR is used as known text to copy into free objects so 37 * that modifications after frees can be detected. 38 */ 39 #define WEIRD_ADDR 0xdeadbeef 40 #define MAX_COPY 32 41 42 /* 43 * Normally the first word of the structure is used to hold the list 44 * pointer for free objects. However, when running with diagnostics, 45 * we use the third and fourth fields, so as to catch modifications 46 * in the most commonly trashed first two words. 47 */ 48 struct freelist { 49 long spare0; 50 short type; 51 long spare1; 52 caddr_t next; 53 }; 54 #else /* !DIAGNOSTIC */ 55 struct freelist { 56 caddr_t next; 57 }; 58 #endif /* DIAGNOSTIC */ 59 60 /* 61 * Allocate a block of memory 62 */ 63 void * 64 malloc(size, type, flags) 65 unsigned long size; 66 int type, flags; 67 { 68 register struct kmembuckets *kbp; 69 register struct kmemusage *kup; 70 register struct freelist *freep; 71 long indx, npg, alloc, allocsize; 72 int s; 73 caddr_t va, cp, savedlist; 74 #ifdef DIAGNOSTIC 75 long *end, *lp; 76 int copysize; 77 char *savedtype; 78 #endif 79 #ifdef KMEMSTATS 80 register struct kmemstats *ksp = &kmemstats[type]; 81 82 if (((unsigned long)type) > M_LAST) 83 panic("malloc - bogus type"); 84 #endif 85 indx = BUCKETINDX(size); 86 kbp = &bucket[indx]; 87 s = splimp(); 88 #ifdef KMEMSTATS 89 while (ksp->ks_memuse >= ksp->ks_limit) { 90 if (flags & M_NOWAIT) { 91 splx(s); 92 return ((void *) NULL); 93 } 94 if (ksp->ks_limblocks < 65535) 95 ksp->ks_limblocks++; 96 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 97 } 98 #endif 99 #ifdef DIAGNOSTIC 100 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 101 #endif 102 if (kbp->kb_next == NULL) { 103 kbp->kb_last = NULL; 104 if (size > MAXALLOCSAVE) 105 allocsize = roundup(size, CLBYTES); 106 else 107 allocsize = 1 << indx; 108 npg = clrnd(btoc(allocsize)); 109 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), 110 !(flags & M_NOWAIT)); 111 if (va == NULL) { 112 splx(s); 113 return ((void *) NULL); 114 } 115 #ifdef KMEMSTATS 116 kbp->kb_total += kbp->kb_elmpercl; 117 #endif 118 kup = btokup(va); 119 kup->ku_indx = indx; 120 if (allocsize > MAXALLOCSAVE) { 121 if (npg > 65535) 122 panic("malloc: allocation too large"); 123 kup->ku_pagecnt = npg; 124 #ifdef KMEMSTATS 125 ksp->ks_memuse += allocsize; 126 #endif 127 goto out; 128 } 129 #ifdef KMEMSTATS 130 kup->ku_freecnt = kbp->kb_elmpercl; 131 kbp->kb_totalfree += kbp->kb_elmpercl; 132 #endif 133 /* 134 * Just in case we blocked while allocating memory, 135 * and someone else also allocated memory for this 136 * bucket, don't assume the list is still empty. 137 */ 138 savedlist = kbp->kb_next; 139 kbp->kb_next = cp = va + (npg * NBPG) - allocsize; 140 for (;;) { 141 freep = (struct freelist *)cp; 142 #ifdef DIAGNOSTIC 143 /* 144 * Copy in known text to detect modification 145 * after freeing. 146 */ 147 end = (long *)&cp[copysize]; 148 for (lp = (long *)cp; lp < end; lp++) 149 *lp = WEIRD_ADDR; 150 freep->type = M_FREE; 151 #endif /* DIAGNOSTIC */ 152 if (cp <= va) 153 break; 154 cp -= allocsize; 155 freep->next = cp; 156 } 157 freep->next = savedlist; 158 if (kbp->kb_last == NULL) 159 kbp->kb_last = (caddr_t)freep; 160 } 161 va = kbp->kb_next; 162 kbp->kb_next = ((struct freelist *)va)->next; 163 #ifdef DIAGNOSTIC 164 freep = (struct freelist *)va; 165 savedtype = (unsigned)freep->type < M_LAST ? 166 memname[freep->type] : "???"; 167 #if BYTE_ORDER == BIG_ENDIAN 168 freep->type = WEIRD_ADDR >> 16; 169 #endif 170 #if BYTE_ORDER == LITTLE_ENDIAN 171 freep->type = WEIRD_ADDR; 172 #endif 173 if (((long)(&freep->next)) & 0x2) 174 freep->next = (caddr_t)((WEIRD_ADDR >> 16)|(WEIRD_ADDR << 16)); 175 else 176 freep->next = (caddr_t)WEIRD_ADDR; 177 end = (long *)&va[copysize]; 178 for (lp = (long *)va; lp < end; lp++) { 179 if (*lp == WEIRD_ADDR) 180 continue; 181 printf("%s %d of object 0x%x size %d %s %s (0x%x != 0x%x)\n", 182 "Data modified on freelist: word", lp - (long *)va, 183 va, size, "previous type", savedtype, *lp, WEIRD_ADDR); 184 break; 185 } 186 freep->spare0 = 0; 187 #endif /* DIAGNOSTIC */ 188 #ifdef KMEMSTATS 189 kup = btokup(va); 190 if (kup->ku_indx != indx) 191 panic("malloc: wrong bucket"); 192 if (kup->ku_freecnt == 0) 193 panic("malloc: lost data"); 194 kup->ku_freecnt--; 195 kbp->kb_totalfree--; 196 ksp->ks_memuse += 1 << indx; 197 out: 198 kbp->kb_calls++; 199 ksp->ks_inuse++; 200 ksp->ks_calls++; 201 if (ksp->ks_memuse > ksp->ks_maxused) 202 ksp->ks_maxused = ksp->ks_memuse; 203 #else 204 out: 205 #endif 206 splx(s); 207 return ((void *) va); 208 } 209 210 /* 211 * Free a block of memory allocated by malloc. 212 */ 213 void 214 free(addr, type) 215 void *addr; 216 int type; 217 { 218 register struct kmembuckets *kbp; 219 register struct kmemusage *kup; 220 register struct freelist *freep; 221 long size; 222 int s; 223 #ifdef DIAGNOSTIC 224 caddr_t cp; 225 long *end, *lp, alloc, copysize; 226 #endif 227 #ifdef KMEMSTATS 228 register struct kmemstats *ksp = &kmemstats[type]; 229 #endif 230 231 kup = btokup(addr); 232 size = 1 << kup->ku_indx; 233 kbp = &bucket[kup->ku_indx]; 234 s = splimp(); 235 #ifdef DIAGNOSTIC 236 /* 237 * Check for returns of data that do not point to the 238 * beginning of the allocation. 239 */ 240 if (size > NBPG * CLSIZE) 241 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 242 else 243 alloc = addrmask[kup->ku_indx]; 244 if (((u_long)addr & alloc) != 0) 245 panic("free: unaligned addr 0x%x, size %d, type %s, mask %d\n", 246 addr, size, memname[type], alloc); 247 #endif /* DIAGNOSTIC */ 248 if (size > MAXALLOCSAVE) { 249 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 250 #ifdef KMEMSTATS 251 size = kup->ku_pagecnt << PGSHIFT; 252 ksp->ks_memuse -= size; 253 kup->ku_indx = 0; 254 kup->ku_pagecnt = 0; 255 if (ksp->ks_memuse + size >= ksp->ks_limit && 256 ksp->ks_memuse < ksp->ks_limit) 257 wakeup((caddr_t)ksp); 258 ksp->ks_inuse--; 259 kbp->kb_total -= 1; 260 #endif 261 splx(s); 262 return; 263 } 264 freep = (struct freelist *)addr; 265 #ifdef DIAGNOSTIC 266 /* 267 * Check for multiple frees. Use a quick check to see if 268 * it looks free before laboriously searching the freelist. 269 */ 270 if (freep->spare0 == WEIRD_ADDR) { 271 for (cp = kbp->kb_next; cp; cp = *(caddr_t *)cp) { 272 if (addr != cp) 273 continue; 274 printf("multiply freed item 0x%x\n", addr); 275 panic("free: duplicated free"); 276 } 277 } 278 /* 279 * Copy in known text to detect modification after freeing 280 * and to make it look free. Also, save the type being freed 281 * so we can list likely culprit if modification is detected 282 * when the object is reallocated. 283 */ 284 copysize = size < MAX_COPY ? size : MAX_COPY; 285 end = (long *)&((caddr_t)addr)[copysize]; 286 for (lp = (long *)addr; lp < end; lp++) 287 *lp = WEIRD_ADDR; 288 freep->type = type; 289 #endif /* DIAGNOSTIC */ 290 #ifdef KMEMSTATS 291 kup->ku_freecnt++; 292 if (kup->ku_freecnt >= kbp->kb_elmpercl) 293 if (kup->ku_freecnt > kbp->kb_elmpercl) 294 panic("free: multiple frees"); 295 else if (kbp->kb_totalfree > kbp->kb_highwat) 296 kbp->kb_couldfree++; 297 kbp->kb_totalfree++; 298 ksp->ks_memuse -= size; 299 if (ksp->ks_memuse + size >= ksp->ks_limit && 300 ksp->ks_memuse < ksp->ks_limit) 301 wakeup((caddr_t)ksp); 302 ksp->ks_inuse--; 303 #endif 304 if (kbp->kb_next == NULL) 305 kbp->kb_next = addr; 306 else 307 ((struct freelist *)kbp->kb_last)->next = addr; 308 freep->next = NULL; 309 kbp->kb_last = addr; 310 splx(s); 311 } 312 313 /* 314 * Initialize the kernel memory allocator 315 */ 316 kmeminit() 317 { 318 register long indx; 319 int npg; 320 321 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 322 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 323 #endif 324 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 325 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 326 #endif 327 #if (MAXALLOCSAVE < CLBYTES) 328 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 329 #endif 330 npg = VM_KMEM_SIZE/ NBPG; 331 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 332 (vm_size_t)(npg * sizeof(struct kmemusage))); 333 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 334 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); 335 #ifdef KMEMSTATS 336 for (indx = 0; indx < MINBUCKET + 16; indx++) { 337 if (1 << indx >= CLBYTES) 338 bucket[indx].kb_elmpercl = 1; 339 else 340 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 341 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 342 } 343 for (indx = 0; indx < M_LAST; indx++) 344 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 345 #endif 346 } 347