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.33.1.1 (Berkeley) 05/20/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 struct uselist { 61 struct uselist *next; 62 caddr_t mem; 63 long size; 64 long type; 65 } *listhd; 66 67 /* 68 * Allocate a block of memory 69 */ 70 void * 71 malloc(size, type, flags) 72 unsigned long size; 73 int type, flags; 74 { 75 register struct kmembuckets *kbp; 76 register struct kmemusage *kup; 77 register struct freelist *freep; 78 long indx, npg, alloc, allocsize; 79 int s; 80 caddr_t va, cp, savedlist; 81 #ifdef DIAGNOSTIC 82 long *end, *lp; 83 int copysize; 84 char *savedtype; 85 struct uselist *mlp; 86 #endif 87 #ifdef KMEMSTATS 88 register struct kmemstats *ksp = &kmemstats[type]; 89 90 if (((unsigned long)type) > M_LAST) 91 panic("malloc - bogus type"); 92 #endif 93 indx = BUCKETINDX(size); 94 kbp = &bucket[indx]; 95 s = splimp(); 96 #ifdef KMEMSTATS 97 while (ksp->ks_memuse >= ksp->ks_limit) { 98 if (flags & M_NOWAIT) { 99 splx(s); 100 return ((void *) NULL); 101 } 102 if (ksp->ks_limblocks < 65535) 103 ksp->ks_limblocks++; 104 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 105 } 106 #endif 107 #ifdef DIAGNOSTIC 108 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 109 #endif 110 if (kbp->kb_next == NULL) { 111 if (size > MAXALLOCSAVE) 112 allocsize = roundup(size, CLBYTES); 113 else 114 allocsize = 1 << indx; 115 npg = clrnd(btoc(allocsize)); 116 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), 117 !(flags & M_NOWAIT)); 118 if (va == NULL) { 119 splx(s); 120 return ((void *) NULL); 121 } 122 #ifdef KMEMSTATS 123 kbp->kb_total += kbp->kb_elmpercl; 124 #endif 125 kup = btokup(va); 126 kup->ku_indx = indx; 127 if (allocsize > MAXALLOCSAVE) { 128 if (npg > 65535) 129 panic("malloc: allocation too large"); 130 kup->ku_pagecnt = npg; 131 #ifdef KMEMSTATS 132 ksp->ks_memuse += allocsize; 133 #endif 134 goto out; 135 } 136 #ifdef KMEMSTATS 137 kup->ku_freecnt = kbp->kb_elmpercl; 138 kbp->kb_totalfree += kbp->kb_elmpercl; 139 #endif 140 /* 141 * Just in case we blocked while allocating memory, 142 * and someone else also allocated memory for this 143 * bucket, don't assume the list is still empty. 144 */ 145 savedlist = kbp->kb_next; 146 kbp->kb_next = cp = va + (npg * NBPG) - allocsize; 147 for (;;) { 148 freep = (struct freelist *)cp; 149 #ifdef DIAGNOSTIC 150 /* 151 * Copy in known text to detect modification 152 * after freeing. 153 */ 154 end = (long *)&cp[copysize]; 155 for (lp = (long *)cp; lp < end; lp++) 156 *lp = WEIRD_ADDR; 157 freep->type = M_FREE; 158 #endif /* DIAGNOSTIC */ 159 if (cp <= va) 160 break; 161 cp -= allocsize; 162 freep->next = cp; 163 } 164 freep->next = savedlist; 165 } 166 va = kbp->kb_next; 167 kbp->kb_next = ((struct freelist *)va)->next; 168 #ifdef DIAGNOSTIC 169 freep = (struct freelist *)va; 170 savedtype = (unsigned)freep->type < M_LAST ? 171 memname[freep->type] : "???"; 172 #if BYTE_ORDER == BIG_ENDIAN 173 freep->type = WEIRD_ADDR >> 16; 174 #endif 175 #if BYTE_ORDER == LITTLE_ENDIAN 176 freep->type = WEIRD_ADDR; 177 #endif 178 if (((long)(&freep->next)) & 0x2) 179 freep->next = (caddr_t)((WEIRD_ADDR >> 16)|(WEIRD_ADDR << 16)); 180 else 181 freep->next = (caddr_t)WEIRD_ADDR; 182 end = (long *)&va[copysize]; 183 for (lp = (long *)va; lp < end; lp++) { 184 if (*lp == WEIRD_ADDR) 185 continue; 186 printf("%s %d of object 0x%x size %d %s %s (0x%x != 0x%x)\n", 187 "Data modified on freelist: word", lp - (long *)va, 188 va, size, "previous type", savedtype, *lp, WEIRD_ADDR); 189 for (mlp = listhd; mlp; mlp = mlp->next) { 190 if (mlp->mem + 128 != va) 191 continue; 192 printf("previous element 0x%x, size %d, type %s\n", 193 mlp->mem, mlp->size, memname[mlp->type]); 194 } 195 break; 196 } 197 freep->spare0 = 0; 198 #endif /* DIAGNOSTIC */ 199 #ifdef KMEMSTATS 200 kup = btokup(va); 201 if (kup->ku_indx != indx) 202 panic("malloc: wrong bucket"); 203 if (kup->ku_freecnt == 0) 204 panic("malloc: lost data"); 205 kup->ku_freecnt--; 206 kbp->kb_totalfree--; 207 ksp->ks_memuse += 1 << indx; 208 out: 209 kbp->kb_calls++; 210 ksp->ks_inuse++; 211 ksp->ks_calls++; 212 if (ksp->ks_memuse > ksp->ks_maxused) 213 ksp->ks_maxused = ksp->ks_memuse; 214 #else 215 out: 216 #endif 217 if (size > 64 && size <= 128) { 218 mlp = (struct uselist *)malloc(sizeof(*mlp), M_TEMP, M_WAITOK); 219 mlp->type = type; 220 mlp->size = size; 221 mlp->mem = va; 222 mlp->next = listhd; 223 listhd = mlp; 224 } 225 splx(s); 226 return ((void *) va); 227 } 228 229 /* 230 * Free a block of memory allocated by malloc. 231 */ 232 void 233 free(addr, type) 234 void *addr; 235 int type; 236 { 237 register struct kmembuckets *kbp; 238 register struct kmemusage *kup; 239 register struct freelist *freep; 240 long size; 241 int s; 242 #ifdef DIAGNOSTIC 243 caddr_t cp; 244 long *end, *lp, alloc, copysize; 245 #endif 246 #ifdef KMEMSTATS 247 register struct kmemstats *ksp = &kmemstats[type]; 248 #endif 249 250 kup = btokup(addr); 251 size = 1 << kup->ku_indx; 252 kbp = &bucket[kup->ku_indx]; 253 s = splimp(); 254 if (size == 128) { 255 struct uselist *mlp, *pmlp; 256 257 mlp = listhd; 258 if (mlp->mem == addr) 259 listhd = mlp->next; 260 else for (pmlp = mlp, mlp = mlp->next ; mlp; mlp = mlp->next) { 261 if (mlp->mem == addr) { 262 pmlp->next = mlp->next; 263 break; 264 } 265 pmlp = mlp; 266 } 267 if (mlp == NULL) 268 printf("free: lost type %s size %d\n", memname[type], 269 size); 270 else 271 free(mlp, M_TEMP); 272 } 273 #ifdef DIAGNOSTIC 274 /* 275 * Check for returns of data that do not point to the 276 * beginning of the allocation. 277 */ 278 if (size > NBPG * CLSIZE) 279 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 280 else 281 alloc = addrmask[kup->ku_indx]; 282 if (((u_long)addr & alloc) != 0) 283 panic("free: unaligned addr 0x%x, size %d, type %s, mask %d\n", 284 addr, size, memname[type], alloc); 285 #endif /* DIAGNOSTIC */ 286 if (size > MAXALLOCSAVE) { 287 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 288 #ifdef KMEMSTATS 289 size = kup->ku_pagecnt << PGSHIFT; 290 ksp->ks_memuse -= size; 291 kup->ku_indx = 0; 292 kup->ku_pagecnt = 0; 293 if (ksp->ks_memuse + size >= ksp->ks_limit && 294 ksp->ks_memuse < ksp->ks_limit) 295 wakeup((caddr_t)ksp); 296 ksp->ks_inuse--; 297 kbp->kb_total -= 1; 298 #endif 299 splx(s); 300 return; 301 } 302 freep = (struct freelist *)addr; 303 #ifdef DIAGNOSTIC 304 /* 305 * Check for multiple frees. Use a quick check to see if 306 * it looks free before laboriously searching the freelist. 307 */ 308 if (freep->spare0 == WEIRD_ADDR) { 309 for (cp = kbp->kb_next; cp; cp = *(caddr_t *)cp) { 310 if (addr != cp) 311 continue; 312 printf("multiply freed item 0x%x\n", addr); 313 panic("free: duplicated free"); 314 } 315 } 316 /* 317 * Copy in known text to detect modification after freeing 318 * and to make it look free. Also, save the type being freed 319 * so we can list likely culprit if modification is detected 320 * when the object is reallocated. 321 */ 322 copysize = size < MAX_COPY ? size : MAX_COPY; 323 end = (long *)&((caddr_t)addr)[copysize]; 324 for (lp = (long *)addr; lp < end; lp++) 325 *lp = WEIRD_ADDR; 326 freep->type = type; 327 #endif /* DIAGNOSTIC */ 328 #ifdef KMEMSTATS 329 kup->ku_freecnt++; 330 if (kup->ku_freecnt >= kbp->kb_elmpercl) 331 if (kup->ku_freecnt > kbp->kb_elmpercl) 332 panic("free: multiple frees"); 333 else if (kbp->kb_totalfree > kbp->kb_highwat) 334 kbp->kb_couldfree++; 335 kbp->kb_totalfree++; 336 ksp->ks_memuse -= size; 337 if (ksp->ks_memuse + size >= ksp->ks_limit && 338 ksp->ks_memuse < ksp->ks_limit) 339 wakeup((caddr_t)ksp); 340 ksp->ks_inuse--; 341 #endif 342 freep->next = kbp->kb_next; 343 kbp->kb_next = addr; 344 splx(s); 345 } 346 347 /* 348 * Initialize the kernel memory allocator 349 */ 350 kmeminit() 351 { 352 register long indx; 353 int npg; 354 355 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 356 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 357 #endif 358 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 359 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 360 #endif 361 #if (MAXALLOCSAVE < CLBYTES) 362 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 363 #endif 364 npg = VM_KMEM_SIZE/ NBPG; 365 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 366 (vm_size_t)(npg * sizeof(struct kmemusage))); 367 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 368 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); 369 #ifdef KMEMSTATS 370 for (indx = 0; indx < MINBUCKET + 16; indx++) { 371 if (1 << indx >= CLBYTES) 372 bucket[indx].kb_elmpercl = 1; 373 else 374 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 375 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 376 } 377 for (indx = 0; indx < M_LAST; indx++) 378 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 379 #endif 380 } 381