Mercurial > hg > nginx-vendor-0-5

comparison src/core/ngx_slab.c @ 258:6ae1357b7b7c NGINX_0_4_14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.4.14 *) Feature: the "proxy_pass_error_message" directive in IMAP/POP3 proxy. *) Feature: now configure detects system PCRE library on FreeBSD, Linux, and NetBSD. *) Bugfix: ngx_http_perl_module did not work with perl built with the threads support; bug appeared in 0.3.38. *) Bugfix: ngx_http_perl_module did not work if perl was called recursively. *) Bugfix: nginx ignored a host name in an request line. *) Bugfix: a worker process may got caught in an endless loop, if a FastCGI server sent too many data to the stderr. *) Bugfix: the $upstream_response_time variable may be negative if the system time was changed backward. *) Bugfix: the "Auth-Login-Attempt" parameter was not sent to IMAP/POP3 proxy authentication server when POP3 was used. *) Bugfix: a segmentation fault might occur if connect to IMAP/POP3 proxy authentication server failed.
author Igor Sysoev <http://sysoev.ru>
date Mon, 27 Nov 2006 00:00:00 +0300
parents
children 0effe91f6083
comparison
equal deleted inserted replaced
257:0e566ee1bcd5 258:6ae1357b7b7c
1
2 /*
3 * Copyright (C) Igor Sysoev
4 */
5
6 #include <ngx_config.h>
7 #include <ngx_core.h>
8
9 /*
10
11 12
12 2048 2 11
13 1024 4 10
14 512 8 9
15 256 16 8
16
17 128 32 4 32 7
18
19 64 64 8 63 6 1
20 32 128 16 127 5 1
21 16 256 32 254 4 2
22 8 512 64 504 3 8
23
24 */
25
26
27 #define NGX_SLAB_PAGE_MASK 3
28 #define NGX_SLAB_PAGE 0
29 #define NGX_SLAB_BIG 1
30 #define NGX_SLAB_EXACT 2
31 #define NGX_SLAB_SMALL 3
32
33 #if (NGX_PTR_SIZE == 4)
34
35 #define NGX_SLAB_PAGE_FREE 0
36 #define NGX_SLAB_PAGE_BUSY 0xffffffff
37 #define NGX_SLAB_PAGE_START 0x80000000
38
39 #define NGX_SLAB_SHIFT_MASK 0x0000000f
40 #define NGX_SLAB_MAP_MASK 0xffff0000
41 #define NGX_SLAB_MAP_SHIFT 16
42
43 #define NGX_SLAB_BUSY 0xffffffff
44
45 #else /* (NGX_PTR_SIZE == 8) */
46
47 #define NGX_SLAB_PAGE_FREE 0
48 #define NGX_SLAB_PAGE_BUSY 0xffffffffffffffff
49 #define NGX_SLAB_PAGE_START 0x8000000000000000
50
51 #define NGX_SLAB_SHIFT_MASK 0x000000000000000f
52 #define NGX_SLAB_MAP_MASK 0xffffffff00000000
53 #define NGX_SLAB_MAP_SHIFT 32
54
55 #define NGX_SLAB_BUSY 0xffffffffffffffff
56
57 #endif
58
59
60 #if (NGX_DEBUG_MALLOC)
61 #define ngx_slab_junk(p, size) ngx_memset(p, 0xD0, size)
62 #else
63 #define ngx_slab_junk(p, size)
64 #endif
65
66 static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool,
67 ngx_uint_t pages);
68 static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
69 ngx_uint_t pages);
70
71
72 static ngx_uint_t ngx_slab_max_size;
73 static ngx_uint_t ngx_slab_exact_size;
74 static ngx_uint_t ngx_slab_exact_shift;
75
76
77 void
78 ngx_slab_init(ngx_slab_pool_t *pool)
79 {
80 u_char *p;
81 size_t size;
82 ngx_int_t m;
83 ngx_uint_t i, n, pages;
84 ngx_slab_page_t *slots;
85
86 /* STUB */
87 if (ngx_slab_max_size == 0) {
88 ngx_slab_max_size = ngx_pagesize / 2;
89 ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
90 for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
91 /* void */
92 }
93 }
94 /**/
95
96 pool->min_size = 1 << pool->min_shift;
97
98 p = (u_char *) pool + sizeof(ngx_slab_pool_t);
99 size = pool->end - p;
100
101 ngx_slab_junk(p, size);
102
103 slots = (ngx_slab_page_t *) p;
104 n = ngx_pagesize_shift - pool->min_shift;
105
106 for (i = 0; i < n; i++) {
107 slots[i].slab = 0;
108 slots[i].next = &slots[i];
109 slots[i].prev = 0;
110 }
111
112 p += n * sizeof(ngx_slab_page_t);
113
114 /* STUB: possible overflow on 64-bit platform */
115 pages = (ngx_uint_t) ((uint64_t) size * ngx_pagesize
116 / (ngx_pagesize + sizeof(ngx_slab_page_t))
117 / ngx_pagesize);
118
119 ngx_memzero(p, pages * sizeof(ngx_slab_page_t));
120
121 pool->pages = (ngx_slab_page_t *) p;
122
123 pool->free.prev = 0;
124 pool->free.next = (ngx_slab_page_t *) p;
125
126 pool->pages->slab = pages;
127 pool->pages->next = &pool->free;
128 pool->pages->prev = (uintptr_t) &pool->free;
129
130 pool->start = (u_char *)
131 ngx_align((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
132 ngx_pagesize);
133
134 m = pages - (pool->end - pool->start) / ngx_pagesize;
135 if (m > 0) {
136 pages -= m;
137 pool->pages->slab = pages;
138 }
139
140 #if 0
141 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "slab: %p, %p, %ui, %d",
142 pool, pool->start, pages,
143 (pool->end - pool->start) / ngx_pagesize - pages);
144 #endif
145 }
146
147
148 void *
149 ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
150 {
151 size_t s;
152 uintptr_t p, mask, *bitmap;
153 ngx_uint_t i, n, m, slot, shift, map;
154 ngx_slab_page_t *page, *prev, *slots;
155
156 ngx_shmtx_lock(&pool->mutex);
157
158 if (size >= ngx_slab_max_size) {
159 page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)
160 >> ngx_pagesize_shift);
161 if (page) {
162 p = (page - pool->pages) << ngx_pagesize_shift;
163 p += (uintptr_t) pool->start;
164
165 } else {
166 p = 0;
167 }
168
169 goto done;
170 }
171
172 if (size > pool->min_size) {
173 shift = 1;
174 for (s = size - 1; s >>= 1; shift++) { /* void */ }
175 slot = shift - pool->min_shift;
176
177 } else {
178 size = pool->min_size;
179 shift = pool->min_shift;
180 slot = 0;
181 }
182
183 ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
184 "slab alloc: %uz slot: %ui", size, slot);
185
186 slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));
187 page = slots[slot].next;
188
189 #if 0
190 ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
191 "slab alloc: page %p next: %p", page, page->next);
192 #endif
193
194 if (page->next != page) {
195
196 if (size < ngx_slab_exact_size) {
197
198 do {
199 p = (page - pool->pages) << ngx_pagesize_shift;
200 bitmap = (uintptr_t *) (pool->start + p);
201
202 map = (1 << (ngx_pagesize_shift - shift))
203 / (sizeof(uintptr_t) * 8);
204
205 for (n = 0; n < map; n++) {
206
207 if (bitmap[n] != NGX_SLAB_BUSY) {
208
209 for (m = 1, i = 0; m; m <<= 1, i++) {
210 if ((bitmap[n] & m)) {
211 continue;
212 }
213
214 bitmap[n] |= m;
215 i <<= shift;
216
217 if (bitmap[n] == NGX_SLAB_BUSY) {
218 for (n = n + 1; n < map; n++) {
219 if (bitmap[n] != NGX_SLAB_BUSY) {
220 p = (uintptr_t) bitmap + i;
221
222 goto done;
223 }
224 }
225
226 prev = (ngx_slab_page_t *)
227 (page->prev & ~NGX_SLAB_PAGE_MASK);
228 prev->next = page->next;
229 page->next->prev = page->prev;
230
231 page->next = NULL;
232 page->prev = NGX_SLAB_SMALL;
233 }
234
235 p = (uintptr_t) bitmap + i;
236
237 goto done;
238 }
239 }
240 }
241
242 page = page->next;
243
244 } while (page);
245
246 } else if (size == ngx_slab_exact_size) {
247
248 do {
249 if (page->slab != NGX_SLAB_BUSY) {
250
251 for (m = 1, i = 0; m; m <<= 1, i++) {
252 if ((page->slab & m)) {
253 continue;
254 }
255
256 page->slab |= m;
257
258 if (page->slab == NGX_SLAB_BUSY) {
259 prev = (ngx_slab_page_t *)
260 (page->prev & ~NGX_SLAB_PAGE_MASK);
261 prev->next = page->next;
262 page->next->prev = page->prev;
263
264 page->next = NULL;
265 page->prev = NGX_SLAB_EXACT;
266 }
267
268 p = (page - pool->pages) << ngx_pagesize_shift;
269 p += i << shift;
270 p += (uintptr_t) pool->start;
271
272 goto done;
273 }
274 }
275
276 page = page->next;
277
278 } while (page);
279
280 } else { /* size < ngx_pagesize */
281
282 n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
283 n = 1 << n;
284 n = (1 << n) - 1;
285 mask = n << NGX_SLAB_MAP_SHIFT;
286
287 do {
288 if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {
289
290 for (m = 1 << NGX_SLAB_MAP_SHIFT, i = 0;
291 m & mask;
292 m <<= 1, i++)
293 {
294 if ((page->slab & m)) {
295 continue;
296 }
297
298 page->slab |= m;
299
300 if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
301 prev = (ngx_slab_page_t *)
302 (page->prev & ~NGX_SLAB_PAGE_MASK);
303 prev->next = page->next;
304 page->next->prev = page->prev;
305
306 page->next = NULL;
307 page->prev = NGX_SLAB_BIG;
308 }
309
310 p = (page - pool->pages) << ngx_pagesize_shift;
311 p += i << shift;
312 p += (uintptr_t) pool->start;
313
314 goto done;
315 }
316 }
317
318 page = page->next;
319
320 } while (page);
321 }
322 }
323
324 page = ngx_slab_alloc_pages(pool, 1);
325
326 if (page) {
327 if (size < ngx_slab_exact_size) {
328 p = (page - pool->pages) << ngx_pagesize_shift;
329 bitmap = (uintptr_t *) (pool->start + p);
330
331 s = 1 << shift;
332 n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;
333
334 if (n == 0) {
335 n = 1;
336 }
337
338 bitmap[0] = (2 << n) - 1;
339
340 map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
341
342 for (i = 1; i < map; i++) {
343 bitmap[i] = 0;
344 }
345
346 page->slab = shift;
347 page->next = &slots[slot];
348 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
349
350 slots[slot].next = page;
351
352 p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
353 p += (uintptr_t) pool->start;
354
355 goto done;
356
357 } else if (size == ngx_slab_exact_size) {
358
359 page->slab = 1;
360 page->next = &slots[slot];
361 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
362
363 slots[slot].next = page;
364
365 p = (page - pool->pages) << ngx_pagesize_shift;
366 p += (uintptr_t) pool->start;
367
368 goto done;
369
370 } else { /* size < ngx_pagesize */
371
372 page->slab = (1 << NGX_SLAB_MAP_SHIFT) | shift;
373 page->next = &slots[slot];
374 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
375
376 slots[slot].next = page;
377
378 p = (page - pool->pages) << ngx_pagesize_shift;
379 p += (uintptr_t) pool->start;
380
381 goto done;
382 }
383 }
384
385 p = 0;
386
387 done:
388
389 ngx_shmtx_unlock(&pool->mutex);
390
391 ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);
392
393 return (void *) p;
394 }
395
396
397 void
398 ngx_slab_free(ngx_slab_pool_t *pool, void *p)
399 {
400 size_t size;
401 uintptr_t slab, *bitmap;
402 ngx_uint_t n, m, type, slot, shift, map;
403 ngx_slab_page_t *slots, *page;
404
405 ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);
406
407 ngx_shmtx_lock(&pool->mutex);
408
409 if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
410 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
411 "ngx_slab_free(): outside of pool");
412 goto fail;
413 }
414
415 n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
416 page = &pool->pages[n];
417 slab = page->slab;
418 type = page->prev & NGX_SLAB_PAGE_MASK;
419
420 switch (type) {
421
422 case NGX_SLAB_SMALL:
423
424 shift = slab & NGX_SLAB_SHIFT_MASK;
425 size = 1 << shift;
426
427 if ((uintptr_t) p & (size - 1)) {
428 goto wrong_chunk;
429 }
430
431 n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
432 m = 1 << (n & (sizeof(uintptr_t) * 8 - 1));
433 n /= (sizeof(uintptr_t) * 8);
434 bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));
435
436 if (bitmap[n] & m) {
437
438 if (page->next == NULL) {
439 slots = (ngx_slab_page_t *)
440 ((u_char *) pool + sizeof(ngx_slab_pool_t));
441 slot = shift - pool->min_shift;
442
443 page->next = slots[slot].next;
444 slots[slot].next = page;
445
446 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
447 page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
448 }
449
450 bitmap[n] &= ~m;
451
452 n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);
453
454 if (n == 0) {
455 n = 1;
456 }
457
458 if (bitmap[0] & ~((1 << n) - 1)) {
459 goto done;
460 }
461
462 map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
463
464 for (n = 1; n < map; n++) {
465 if (bitmap[n]) {
466 goto done;
467 }
468 }
469
470 ngx_slab_free_pages(pool, page, 1);
471
472 goto done;
473 }
474
475 goto chunk_already_free;
476
477 case NGX_SLAB_EXACT:
478
479 m = 1 << (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
480 size = ngx_slab_exact_size;
481
482 if ((uintptr_t) p & (size - 1)) {
483 goto wrong_chunk;
484 }
485
486 if (slab & m) {
487 if (slab == NGX_SLAB_BUSY) {
488 slots = (ngx_slab_page_t *)
489 ((u_char *) pool + sizeof(ngx_slab_pool_t));
490 slot = ngx_slab_exact_shift - pool->min_shift;
491
492 page->next = slots[slot].next;
493 slots[slot].next = page;
494
495 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
496 page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
497 }
498
499 page->slab &= ~m;
500
501 if (page->slab) {
502 goto done;
503 }
504
505 ngx_slab_free_pages(pool, page, 1);
506
507 goto done;
508 }
509
510 goto chunk_already_free;
511
512 case NGX_SLAB_BIG:
513
514 shift = slab & NGX_SLAB_SHIFT_MASK;
515 size = 1 << shift;
516
517 if ((uintptr_t) p & (size - 1)) {
518 goto wrong_chunk;
519 }
520
521 m = 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
522 + NGX_SLAB_MAP_SHIFT);
523
524 if (slab & m) {
525
526 if (page->next == NULL) {
527 slots = (ngx_slab_page_t *)
528 ((u_char *) pool + sizeof(ngx_slab_pool_t));
529 slot = shift - pool->min_shift;
530
531 page->next = slots[slot].next;
532 slots[slot].next = page;
533
534 page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
535 page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
536 }
537
538 page->slab &= ~m;
539
540 if (page->slab & NGX_SLAB_MAP_MASK) {
541 goto done;
542 }
543
544 ngx_slab_free_pages(pool, page, 1);
545
546 goto done;
547 }
548
549 goto chunk_already_free;
550
551 case NGX_SLAB_PAGE:
552
553 if ((uintptr_t) p & (ngx_pagesize - 1)) {
554 goto wrong_chunk;
555 }
556
557 if (slab == NGX_SLAB_PAGE_FREE) {
558 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
559 "ngx_slab_free(): page is already free");
560 goto fail;
561 }
562
563 if (slab == NGX_SLAB_PAGE_BUSY) {
564 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
565 "ngx_slab_free(): pointer to wrong page");
566 goto fail;
567 }
568
569 n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
570 size = slab & ~NGX_SLAB_PAGE_START;
571
572 ngx_slab_free_pages(pool, &pool->pages[n], size);
573
574 size <<= ngx_pagesize_shift;
575
576 goto done;
577 }
578
579 /* not reached */
580
581 return;
582
583 done:
584
585 ngx_slab_junk(p, size);
586
587 ngx_shmtx_unlock(&pool->mutex);
588
589 return;
590
591 wrong_chunk:
592
593 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
594 "ngx_slab_free(): pointer to wrong chunk");
595
596 goto fail;
597
598 chunk_already_free:
599
600 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
601 "ngx_slab_free(): chunk is already free");
602
603 fail:
604
605 ngx_shmtx_unlock(&pool->mutex);
606
607 return;
608 }
609
610
611 static ngx_slab_page_t *
612 ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
613 {
614 ngx_slab_page_t *page, *p;
615
616 for (page = pool->free.next; page != &pool->free; page = page->next) {
617
618 if (page->slab >= pages) {
619
620 if (page->slab > pages) {
621 page[pages].slab = page->slab - pages;
622 page[pages].next = page->next;
623 page[pages].prev = page->prev;
624
625 p = (ngx_slab_page_t *) page->prev;
626 p->next = &page[pages];
627 page->next->prev = (uintptr_t) &page[pages];
628
629 } else {
630 p = (ngx_slab_page_t *) page->prev;
631 p->next = page->next;
632 page->next->prev = page->prev;
633 }
634
635 page->slab = pages | NGX_SLAB_PAGE_START;
636
637 #if (NGX_DEBUG)
638 page->next = NULL;
639 page->prev = NGX_SLAB_PAGE;
640 #endif
641
642 if (--pages == 0) {
643 return page;
644 }
645
646 for (p = page + 1; pages; pages--) {
647 p->slab = NGX_SLAB_PAGE_BUSY;
648 #if (NGX_DEBUG)
649 p->next = NULL;
650 p->prev = NGX_SLAB_PAGE;
651 #endif
652 p++;
653 }
654
655 return page;
656 }
657 }
658
659 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, NGX_ENOMEM,
660 "ngx_slab_alloc(): failed");
661 return NULL;
662 }
663
664
665 static void
666 ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
667 ngx_uint_t pages)
668 {
669 ngx_slab_page_t *prev;
670
671 page->slab = pages--;
672
673 if (pages) {
674 ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
675 }
676
677 prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
678 prev->next = page->next;
679
680 page->next = pool->free.next;
681 pool->free.next = page;
682
683 page->prev = page->next->prev;
684 page->next->prev = (uintptr_t) page;
685 }