1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 /*
7 ** Thread safe versions of malloc, free, realloc, calloc and cfree.
8 */
9
10 #include "primpl.h"
11
12 #ifdef _PR_ZONE_ALLOCATOR
13
14 /*
15 ** The zone allocator code must use native mutexes and cannot
16 ** use PRLocks because PR_NewLock calls PR_Calloc, resulting
17 ** in cyclic dependency of initialization.
18 */
19
20 #include <string.h>
21
22 union memBlkHdrUn;
23
24 typedef struct MemoryZoneStr {
25 union memBlkHdrUn *head; /* free list */
26 pthread_mutex_t lock;
27 size_t blockSize; /* size of blocks on this free list */
28 PRUint32 locked; /* current state of lock */
29 PRUint32 contention; /* counter: had to wait for lock */
30 PRUint32 hits; /* allocated from free list */
31 PRUint32 misses; /* had to call malloc */
32 PRUint32 elements; /* on free list */
33 } MemoryZone;
34
35 typedef union memBlkHdrUn {
36 unsigned char filler[48]; /* fix the size of this beast */
37 struct memBlkHdrStr {
38 union memBlkHdrUn *next;
39 MemoryZone *zone;
40 size_t blockSize;
41 size_t requestedSize;
42 PRUint32 magic;
43 } s;
44 } MemBlockHdr;
45
46 #define MEM_ZONES 7
47 #define THREAD_POOLS 11 /* prime number for modulus */
48 #define ZONE_MAGIC 0x0BADC0DE
49
50 static MemoryZone zones[MEM_ZONES][THREAD_POOLS];
51
52 static PRBool use_zone_allocator = PR_FALSE;
53
54 static void pr_ZoneFree(void *ptr);
55
56 void
_PR_DestroyZones(void)57 _PR_DestroyZones(void)
58 {
59 int i, j;
60
61 if (!use_zone_allocator) {
62 return;
63 }
64
65 for (j = 0; j < THREAD_POOLS; j++) {
66 for (i = 0; i < MEM_ZONES; i++) {
67 MemoryZone *mz = &zones[i][j];
68 pthread_mutex_destroy(&mz->lock);
69 while (mz->head) {
70 MemBlockHdr *hdr = mz->head;
71 mz->head = hdr->s.next; /* unlink it */
72 free(hdr);
73 mz->elements--;
74 }
75 }
76 }
77 use_zone_allocator = PR_FALSE;
78 }
79
80 /*
81 ** pr_FindSymbolInProg
82 **
83 ** Find the specified data symbol in the program and return
84 ** its address.
85 */
86
87 #ifdef HAVE_DLL
88
89 #if defined(USE_DLFCN) && !defined(NO_DLOPEN_NULL)
90
91 #include <dlfcn.h>
92
93 static void *
pr_FindSymbolInProg(const char * name)94 pr_FindSymbolInProg(const char *name)
95 {
96 void *h;
97 void *sym;
98
99 h = dlopen(0, RTLD_LAZY);
100 if (h == NULL) {
101 return NULL;
102 }
103 sym = dlsym(h, name);
104 (void)dlclose(h);
105 return sym;
106 }
107
108 #elif defined(USE_HPSHL)
109
110 #include <dl.h>
111
112 static void *
pr_FindSymbolInProg(const char * name)113 pr_FindSymbolInProg(const char *name)
114 {
115 shl_t h = NULL;
116 void *sym;
117
118 if (shl_findsym(&h, name, TYPE_DATA, &sym) == -1) {
119 return NULL;
120 }
121 return sym;
122 }
123
124 #elif defined(USE_MACH_DYLD) || defined(NO_DLOPEN_NULL)
125
126 static void *
pr_FindSymbolInProg(const char * name)127 pr_FindSymbolInProg(const char *name)
128 {
129 /* FIXME: not implemented */
130 return NULL;
131 }
132
133 #else
134
135 #error "The zone allocator is not supported on this platform"
136
137 #endif
138
139 #else /* !defined(HAVE_DLL) */
140
141 static void *
pr_FindSymbolInProg(const char * name)142 pr_FindSymbolInProg(const char *name)
143 {
144 /* can't be implemented */
145 return NULL;
146 }
147
148 #endif /* HAVE_DLL */
149
150 void
_PR_InitZones(void)151 _PR_InitZones(void)
152 {
153 int i, j;
154 char *envp;
155 PRBool *sym;
156
157 if ((sym = (PRBool *)pr_FindSymbolInProg("nspr_use_zone_allocator")) != NULL) {
158 use_zone_allocator = *sym;
159 } else if ((envp = getenv("NSPR_USE_ZONE_ALLOCATOR")) != NULL) {
160 use_zone_allocator = (atoi(envp) == 1);
161 }
162
163 if (!use_zone_allocator) {
164 return;
165 }
166
167 for (j = 0; j < THREAD_POOLS; j++) {
168 for (i = 0; i < MEM_ZONES; i++) {
169 MemoryZone *mz = &zones[i][j];
170 int rv = pthread_mutex_init(&mz->lock, NULL);
171 PR_ASSERT(0 == rv);
172 if (rv != 0) {
173 goto loser;
174 }
175 mz->blockSize = 16 << ( 2 * i);
176 }
177 }
178 return;
179
180 loser:
181 _PR_DestroyZones();
182 return;
183 }
184
185 PR_IMPLEMENT(void)
PR_FPrintZoneStats(PRFileDesc * debug_out)186 PR_FPrintZoneStats(PRFileDesc *debug_out)
187 {
188 int i, j;
189
190 for (j = 0; j < THREAD_POOLS; j++) {
191 for (i = 0; i < MEM_ZONES; i++) {
192 MemoryZone *mz = &zones[i][j];
193 MemoryZone zone = *mz;
194 if (zone.elements || zone.misses || zone.hits) {
195 PR_fprintf(debug_out,
196 "pool: %d, zone: %d, size: %d, free: %d, hit: %d, miss: %d, contend: %d\n",
197 j, i, zone.blockSize, zone.elements,
198 zone.hits, zone.misses, zone.contention);
199 }
200 }
201 }
202 }
203
204 static void *
pr_ZoneMalloc(PRUint32 size)205 pr_ZoneMalloc(PRUint32 size)
206 {
207 void *rv;
208 unsigned int zone;
209 size_t blockSize;
210 MemBlockHdr *mb, *mt;
211 MemoryZone *mz;
212
213 /* Always allocate a non-zero amount of bytes */
214 if (size < 1) {
215 size = 1;
216 }
217 for (zone = 0, blockSize = 16; zone < MEM_ZONES; ++zone, blockSize <<= 2) {
218 if (size <= blockSize) {
219 break;
220 }
221 }
222 if (zone < MEM_ZONES) {
223 pthread_t me = pthread_self();
224 unsigned int pool = (PRUptrdiff)me % THREAD_POOLS;
225 PRUint32 wasLocked;
226 mz = &zones[zone][pool];
227 wasLocked = mz->locked;
228 pthread_mutex_lock(&mz->lock);
229 mz->locked = 1;
230 if (wasLocked) {
231 mz->contention++;
232 }
233 if (mz->head) {
234 mb = mz->head;
235 PR_ASSERT(mb->s.magic == ZONE_MAGIC);
236 PR_ASSERT(mb->s.zone == mz);
237 PR_ASSERT(mb->s.blockSize == blockSize);
238 PR_ASSERT(mz->blockSize == blockSize);
239
240 mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
241 PR_ASSERT(mt->s.magic == ZONE_MAGIC);
242 PR_ASSERT(mt->s.zone == mz);
243 PR_ASSERT(mt->s.blockSize == blockSize);
244
245 mz->hits++;
246 mz->elements--;
247 mz->head = mb->s.next; /* take off free list */
248 mz->locked = 0;
249 pthread_mutex_unlock(&mz->lock);
250
251 mt->s.next = mb->s.next = NULL;
252 mt->s.requestedSize = mb->s.requestedSize = size;
253
254 rv = (void *)(mb + 1);
255 return rv;
256 }
257
258 mz->misses++;
259 mz->locked = 0;
260 pthread_mutex_unlock(&mz->lock);
261
262 mb = (MemBlockHdr *)malloc(blockSize + 2 * (sizeof *mb));
263 if (!mb) {
264 PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
265 return NULL;
266 }
267 mb->s.next = NULL;
268 mb->s.zone = mz;
269 mb->s.magic = ZONE_MAGIC;
270 mb->s.blockSize = blockSize;
271 mb->s.requestedSize = size;
272
273 mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
274 memcpy(mt, mb, sizeof *mb);
275
276 rv = (void *)(mb + 1);
277 return rv;
278 }
279
280 /* size was too big. Create a block with no zone */
281 blockSize = (size & 15) ? size + 16 - (size & 15) : size;
282 mb = (MemBlockHdr *)malloc(blockSize + 2 * (sizeof *mb));
283 if (!mb) {
284 PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
285 return NULL;
286 }
287 mb->s.next = NULL;
288 mb->s.zone = NULL;
289 mb->s.magic = ZONE_MAGIC;
290 mb->s.blockSize = blockSize;
291 mb->s.requestedSize = size;
292
293 mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
294 memcpy(mt, mb, sizeof *mb);
295
296 rv = (void *)(mb + 1);
297 return rv;
298 }
299
300
301 static void *
pr_ZoneCalloc(PRUint32 nelem,PRUint32 elsize)302 pr_ZoneCalloc(PRUint32 nelem, PRUint32 elsize)
303 {
304 PRUint32 size = nelem * elsize;
305 void *p = pr_ZoneMalloc(size);
306 if (p) {
307 memset(p, 0, size);
308 }
309 return p;
310 }
311
312 static void *
pr_ZoneRealloc(void * oldptr,PRUint32 bytes)313 pr_ZoneRealloc(void *oldptr, PRUint32 bytes)
314 {
315 void *rv;
316 MemBlockHdr *mb;
317 int ours;
318 MemBlockHdr phony;
319
320 if (!oldptr) {
321 return pr_ZoneMalloc(bytes);
322 }
323 mb = (MemBlockHdr *)((char *)oldptr - (sizeof *mb));
324 if (mb->s.magic != ZONE_MAGIC) {
325 /* Maybe this just came from ordinary malloc */
326 #ifdef DEBUG
327 fprintf(stderr,
328 "Warning: reallocing memory block %p from ordinary malloc\n",
329 oldptr);
330 #endif
331 /*
332 * We are going to realloc oldptr. If realloc succeeds, the
333 * original value of oldptr will point to freed memory. So this
334 * function must not fail after a successfull realloc call. We
335 * must perform any operation that may fail before the realloc
336 * call.
337 */
338 rv = pr_ZoneMalloc(bytes); /* this may fail */
339 if (!rv) {
340 return rv;
341 }
342
343 /* We don't know how big it is. But we can fix that. */
344 oldptr = realloc(oldptr, bytes);
345 /*
346 * If realloc returns NULL, this function loses the original
347 * value of oldptr. This isn't a leak because the caller of
348 * this function still has the original value of oldptr.
349 */
350 if (!oldptr) {
351 if (bytes) {
352 PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
353 pr_ZoneFree(rv);
354 return oldptr;
355 }
356 }
357 phony.s.requestedSize = bytes;
358 mb = &phony;
359 ours = 0;
360 } else {
361 size_t blockSize = mb->s.blockSize;
362 MemBlockHdr *mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
363
364 PR_ASSERT(mt->s.magic == ZONE_MAGIC);
365 PR_ASSERT(mt->s.zone == mb->s.zone);
366 PR_ASSERT(mt->s.blockSize == blockSize);
367
368 if (bytes <= blockSize) {
369 /* The block is already big enough. */
370 mt->s.requestedSize = mb->s.requestedSize = bytes;
371 return oldptr;
372 }
373 ours = 1;
374 rv = pr_ZoneMalloc(bytes);
375 if (!rv) {
376 return rv;
377 }
378 }
379
380 if (oldptr && mb->s.requestedSize) {
381 memcpy(rv, oldptr, mb->s.requestedSize);
382 }
383 if (ours) {
384 pr_ZoneFree(oldptr);
385 }
386 else if (oldptr) {
387 free(oldptr);
388 }
389 return rv;
390 }
391
392 static void
pr_ZoneFree(void * ptr)393 pr_ZoneFree(void *ptr)
394 {
395 MemBlockHdr *mb, *mt;
396 MemoryZone *mz;
397 size_t blockSize;
398 PRUint32 wasLocked;
399
400 if (!ptr) {
401 return;
402 }
403
404 mb = (MemBlockHdr *)((char *)ptr - (sizeof *mb));
405
406 if (mb->s.magic != ZONE_MAGIC) {
407 /* maybe this came from ordinary malloc */
408 #ifdef DEBUG
409 fprintf(stderr,
410 "Warning: freeing memory block %p from ordinary malloc\n", ptr);
411 #endif
412 free(ptr);
413 return;
414 }
415
416 blockSize = mb->s.blockSize;
417 mz = mb->s.zone;
418 mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
419 PR_ASSERT(mt->s.magic == ZONE_MAGIC);
420 PR_ASSERT(mt->s.zone == mz);
421 PR_ASSERT(mt->s.blockSize == blockSize);
422 if (!mz) {
423 PR_ASSERT(blockSize > 65536);
424 /* This block was not in any zone. Just free it. */
425 free(mb);
426 return;
427 }
428 PR_ASSERT(mz->blockSize == blockSize);
429 wasLocked = mz->locked;
430 pthread_mutex_lock(&mz->lock);
431 mz->locked = 1;
432 if (wasLocked) {
433 mz->contention++;
434 }
435 mt->s.next = mb->s.next = mz->head; /* put on head of list */
436 mz->head = mb;
437 mz->elements++;
438 mz->locked = 0;
439 pthread_mutex_unlock(&mz->lock);
440 }
441
PR_Malloc(PRUint32 size)442 PR_IMPLEMENT(void *) PR_Malloc(PRUint32 size)
443 {
444 if (!_pr_initialized) {
445 _PR_ImplicitInitialization();
446 }
447
448 return use_zone_allocator ? pr_ZoneMalloc(size) : malloc(size);
449 }
450
PR_Calloc(PRUint32 nelem,PRUint32 elsize)451 PR_IMPLEMENT(void *) PR_Calloc(PRUint32 nelem, PRUint32 elsize)
452 {
453 if (!_pr_initialized) {
454 _PR_ImplicitInitialization();
455 }
456
457 return use_zone_allocator ?
458 pr_ZoneCalloc(nelem, elsize) : calloc(nelem, elsize);
459 }
460
PR_Realloc(void * ptr,PRUint32 size)461 PR_IMPLEMENT(void *) PR_Realloc(void *ptr, PRUint32 size)
462 {
463 if (!_pr_initialized) {
464 _PR_ImplicitInitialization();
465 }
466
467 return use_zone_allocator ? pr_ZoneRealloc(ptr, size) : realloc(ptr, size);
468 }
469
PR_Free(void * ptr)470 PR_IMPLEMENT(void) PR_Free(void *ptr)
471 {
472 if (use_zone_allocator) {
473 pr_ZoneFree(ptr);
474 }
475 else {
476 free(ptr);
477 }
478 }
479
480 #else /* !defined(_PR_ZONE_ALLOCATOR) */
481
482 /*
483 ** The PR_Malloc, PR_Calloc, PR_Realloc, and PR_Free functions simply
484 ** call their libc equivalents now. This may seem redundant, but it
485 ** ensures that we are calling into the same runtime library. On
486 ** Win32, it is possible to have multiple runtime libraries (e.g.,
487 ** objects compiled with /MD and /MDd) in the same process, and
488 ** they maintain separate heaps, which cannot be mixed.
489 */
PR_Malloc(PRUint32 size)490 PR_IMPLEMENT(void *) PR_Malloc(PRUint32 size)
491 {
492 #if defined (WIN16)
493 return PR_MD_malloc( (size_t) size);
494 #else
495 return malloc(size);
496 #endif
497 }
498
PR_Calloc(PRUint32 nelem,PRUint32 elsize)499 PR_IMPLEMENT(void *) PR_Calloc(PRUint32 nelem, PRUint32 elsize)
500 {
501 #if defined (WIN16)
502 return PR_MD_calloc( (size_t)nelem, (size_t)elsize );
503
504 #else
505 return calloc(nelem, elsize);
506 #endif
507 }
508
PR_Realloc(void * ptr,PRUint32 size)509 PR_IMPLEMENT(void *) PR_Realloc(void *ptr, PRUint32 size)
510 {
511 #if defined (WIN16)
512 return PR_MD_realloc( ptr, (size_t) size);
513 #else
514 return realloc(ptr, size);
515 #endif
516 }
517
PR_Free(void * ptr)518 PR_IMPLEMENT(void) PR_Free(void *ptr)
519 {
520 #if defined (WIN16)
521 PR_MD_free( ptr );
522 #else
523 free(ptr);
524 #endif
525 }
526
527 #endif /* _PR_ZONE_ALLOCATOR */
528
529 /*
530 ** Complexity alert!
531 **
532 ** If malloc/calloc/free (etc.) were implemented to use pr lock's then
533 ** the entry points could block when called if some other thread had the
534 ** lock.
535 **
536 ** Most of the time this isn't a problem. However, in the case that we
537 ** are using the thread safe malloc code after PR_Init but before
538 ** PR_AttachThread has been called (on a native thread that nspr has yet
539 ** to be told about) we could get royally screwed if the lock was busy
540 ** and we tried to context switch the thread away. In this scenario
541 ** PR_CURRENT_THREAD() == NULL
542 **
543 ** To avoid this unfortunate case, we use the low level locking
544 ** facilities for malloc protection instead of the slightly higher level
545 ** locking. This makes malloc somewhat faster so maybe it's a good thing
546 ** anyway.
547 */
548 #ifdef _PR_OVERRIDE_MALLOC
549
550 /* Imports */
551 extern void *_PR_UnlockedMalloc(size_t size);
552 extern void *_PR_UnlockedMemalign(size_t alignment, size_t size);
553 extern void _PR_UnlockedFree(void *ptr);
554 extern void *_PR_UnlockedRealloc(void *ptr, size_t size);
555 extern void *_PR_UnlockedCalloc(size_t n, size_t elsize);
556
557 static PRBool _PR_malloc_initialised = PR_FALSE;
558
559 #ifdef _PR_PTHREADS
560 static pthread_mutex_t _PR_MD_malloc_crustylock;
561
562 #define _PR_Lock_Malloc() { \
563 if(PR_TRUE == _PR_malloc_initialised) { \
564 PRStatus rv; \
565 rv = pthread_mutex_lock(&_PR_MD_malloc_crustylock); \
566 PR_ASSERT(0 == rv); \
567 }
568
569 #define _PR_Unlock_Malloc() if(PR_TRUE == _PR_malloc_initialised) { \
570 PRStatus rv; \
571 rv = pthread_mutex_unlock(&_PR_MD_malloc_crustylock); \
572 PR_ASSERT(0 == rv); \
573 } \
574 }
575 #else /* _PR_PTHREADS */
576 static _MDLock _PR_MD_malloc_crustylock;
577
578 #define _PR_Lock_Malloc() { \
579 PRIntn _is; \
580 if(PR_TRUE == _PR_malloc_initialised) { \
581 if (_PR_MD_CURRENT_THREAD() && \
582 !_PR_IS_NATIVE_THREAD( \
583 _PR_MD_CURRENT_THREAD())) \
584 _PR_INTSOFF(_is); \
585 _PR_MD_LOCK(&_PR_MD_malloc_crustylock); \
586 }
587
588 #define _PR_Unlock_Malloc() if(PR_TRUE == _PR_malloc_initialised) { \
589 _PR_MD_UNLOCK(&_PR_MD_malloc_crustylock); \
590 if (_PR_MD_CURRENT_THREAD() && \
591 !_PR_IS_NATIVE_THREAD( \
592 _PR_MD_CURRENT_THREAD())) \
593 _PR_INTSON(_is); \
594 } \
595 }
596 #endif /* _PR_PTHREADS */
597
_PR_MallocInit(void)598 PR_IMPLEMENT(PRStatus) _PR_MallocInit(void)
599 {
600 PRStatus rv = PR_SUCCESS;
601
602 if( PR_TRUE == _PR_malloc_initialised ) {
603 return PR_SUCCESS;
604 }
605
606 #ifdef _PR_PTHREADS
607 {
608 int status;
609 pthread_mutexattr_t mattr;
610
611 status = _PT_PTHREAD_MUTEXATTR_INIT(&mattr);
612 PR_ASSERT(0 == status);
613 status = _PT_PTHREAD_MUTEX_INIT(_PR_MD_malloc_crustylock, mattr);
614 PR_ASSERT(0 == status);
615 status = _PT_PTHREAD_MUTEXATTR_DESTROY(&mattr);
616 PR_ASSERT(0 == status);
617 }
618 #else /* _PR_PTHREADS */
619 _MD_NEW_LOCK(&_PR_MD_malloc_crustylock);
620 #endif /* _PR_PTHREADS */
621
622 if( PR_SUCCESS == rv )
623 {
624 _PR_malloc_initialised = PR_TRUE;
625 }
626
627 return rv;
628 }
629
malloc(size_t size)630 void *malloc(size_t size)
631 {
632 void *p;
633 _PR_Lock_Malloc();
634 p = _PR_UnlockedMalloc(size);
635 _PR_Unlock_Malloc();
636 return p;
637 }
638
free(void * ptr)639 void free(void *ptr)
640 {
641 _PR_Lock_Malloc();
642 _PR_UnlockedFree(ptr);
643 _PR_Unlock_Malloc();
644 }
645
realloc(void * ptr,size_t size)646 void *realloc(void *ptr, size_t size)
647 {
648 void *p;
649 _PR_Lock_Malloc();
650 p = _PR_UnlockedRealloc(ptr, size);
651 _PR_Unlock_Malloc();
652 return p;
653 }
654
calloc(size_t n,size_t elsize)655 void *calloc(size_t n, size_t elsize)
656 {
657 void *p;
658 _PR_Lock_Malloc();
659 p = _PR_UnlockedCalloc(n, elsize);
660 _PR_Unlock_Malloc();
661 return p;
662 }
663
cfree(void * p)664 void cfree(void *p)
665 {
666 _PR_Lock_Malloc();
667 _PR_UnlockedFree(p);
668 _PR_Unlock_Malloc();
669 }
670
_PR_InitMem(void)671 void _PR_InitMem(void)
672 {
673 PRStatus rv;
674 rv = _PR_MallocInit();
675 PR_ASSERT(PR_SUCCESS == rv);
676 }
677
678 #endif /* _PR_OVERRIDE_MALLOC */
679