1 /* $NetBSD: zn_malloc.c,v 1.3 2021/08/14 16:14:58 christos Exp $ */
2
3 /* zn_malloc.c - zone-based malloc routines */
4 /* $OpenLDAP$*/
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 2003-2021 The OpenLDAP Foundation.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted only as authorized by the OpenLDAP
12 * Public License.
13 *
14 * A copy of this license is available in the file LICENSE in the
15 * top-level directory of the distribution or, alternatively, at
16 * <http://www.OpenLDAP.org/license.html>.
17 */
18 /* Portions Copyright 2004 IBM Corporation
19 * All rights reserved.
20 * Redistribution and use in source and binary forms, with or without
21 * modification, are permitted only as authorized by the OpenLDAP
22 * Public License.
23 */
24 /* ACKNOWLEDGEMENTS
25 * This work originally developed by Jong-Hyuk Choi for inclusion in
26 * OpenLDAP Software.
27 */
28
29 #include <sys/cdefs.h>
30 __RCSID("$NetBSD: zn_malloc.c,v 1.3 2021/08/14 16:14:58 christos Exp $");
31
32 #include "portable.h"
33
34 #include <stdio.h>
35 #include <ac/string.h>
36 #include <sys/types.h>
37 #include <fcntl.h>
38
39 #include "slap.h"
40
41 #ifdef SLAP_ZONE_ALLOC
42
43 #include <sys/mman.h>
44
45 static int slap_zone_cmp(const void *v1, const void *v2);
46 void * slap_replenish_zopool(void *ctx);
47
48 static void
slap_zo_release(void * data)49 slap_zo_release(void *data)
50 {
51 struct zone_object *zo = (struct zone_object *)data;
52 ch_free( zo );
53 }
54
55 void
slap_zn_mem_destroy(void * ctx)56 slap_zn_mem_destroy(
57 void *ctx
58 )
59 {
60 struct zone_heap *zh = ctx;
61 int pad = 2*sizeof(int)-1, pad_shift;
62 int order_start = -1, i, j;
63 struct zone_object *zo;
64
65 pad_shift = pad - 1;
66 do {
67 order_start++;
68 } while (pad_shift >>= 1);
69
70 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
71 for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) {
72 zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
73 while (zo) {
74 struct zone_object *zo_tmp = zo;
75 zo = LDAP_LIST_NEXT(zo, zo_link);
76 LDAP_LIST_REMOVE(zo_tmp, zo_link);
77 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
78 }
79 }
80 ch_free(zh->zh_free);
81
82 for (i = 0; i < zh->zh_numzones; i++) {
83 for (j = 0; j < zh->zh_zoneorder - order_start + 1; j++) {
84 ch_free(zh->zh_maps[i][j]);
85 }
86 ch_free(zh->zh_maps[i]);
87 munmap(zh->zh_zones[i], zh->zh_zonesize);
88 ldap_pvt_thread_rdwr_destroy(&zh->zh_znlock[i]);
89 }
90 ch_free(zh->zh_maps);
91 ch_free(zh->zh_zones);
92 ch_free(zh->zh_seqno);
93 ch_free(zh->zh_znlock);
94
95 ldap_avl_free(zh->zh_zonetree, slap_zo_release);
96
97 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
98 while (zo) {
99 struct zone_object *zo_tmp = zo;
100 zo = LDAP_LIST_NEXT(zo, zo_link);
101 if (!zo_tmp->zo_blockhead) {
102 LDAP_LIST_REMOVE(zo_tmp, zo_link);
103 }
104 }
105 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
106 while (zo) {
107 struct zone_object *zo_tmp = zo;
108 zo = LDAP_LIST_NEXT(zo, zo_link);
109 ch_free(zo_tmp);
110 }
111 ldap_pvt_thread_mutex_unlock(&zh->zh_mutex);
112 ldap_pvt_thread_rdwr_destroy(&zh->zh_lock);
113 ldap_pvt_thread_mutex_destroy(&zh->zh_mutex);
114 ch_free(zh);
115 }
116
117 void *
slap_zn_mem_create(ber_len_t initsize,ber_len_t maxsize,ber_len_t deltasize,ber_len_t zonesize)118 slap_zn_mem_create(
119 ber_len_t initsize,
120 ber_len_t maxsize,
121 ber_len_t deltasize,
122 ber_len_t zonesize
123 )
124 {
125 struct zone_heap *zh = NULL;
126 ber_len_t zpad;
127 int pad = 2*sizeof(int)-1, pad_shift;
128 int size_shift;
129 int order = -1, order_start = -1, order_end = -1;
130 int i, j;
131 struct zone_object *zo;
132
133 Debug(LDAP_DEBUG_NONE,
134 "--> slap_zn_mem_create: initsize=%d, maxsize=%d\n",
135 initsize, maxsize );
136 Debug(LDAP_DEBUG_NONE,
137 "++> slap_zn_mem_create: deltasize=%d, zonesize=%d\n",
138 deltasize, zonesize );
139
140 zh = (struct zone_heap *)ch_calloc(1, sizeof(struct zone_heap));
141
142 zh->zh_fd = open("/dev/zero", O_RDWR);
143
144 if ( zonesize ) {
145 zh->zh_zonesize = zonesize;
146 } else {
147 zh->zh_zonesize = SLAP_ZONE_SIZE;
148 }
149
150 zpad = zh->zh_zonesize - 1;
151 zh->zh_numzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
152
153 if ( maxsize && maxsize >= initsize ) {
154 zh->zh_maxzones = ((maxsize + zpad) & ~zpad) / zh->zh_zonesize;
155 } else {
156 zh->zh_maxzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
157 }
158
159 if ( deltasize ) {
160 zh->zh_deltazones = ((deltasize + zpad) & ~zpad) / zh->zh_zonesize;
161 } else {
162 zh->zh_deltazones = ((SLAP_ZONE_DELTA+zpad) & ~zpad) / zh->zh_zonesize;
163 }
164
165 size_shift = zh->zh_zonesize - 1;
166 do {
167 order_end++;
168 } while (size_shift >>= 1);
169
170 pad_shift = pad - 1;
171 do {
172 order_start++;
173 } while (pad_shift >>= 1);
174
175 order = order_end - order_start + 1;
176
177 zh->zh_zones = (void **)ch_malloc(zh->zh_maxzones * sizeof(void*));
178 zh->zh_znlock = (ldap_pvt_thread_rdwr_t *)ch_malloc(
179 zh->zh_maxzones * sizeof(ldap_pvt_thread_rdwr_t *));
180 zh->zh_maps = (unsigned char ***)ch_malloc(
181 zh->zh_maxzones * sizeof(unsigned char**));
182
183 zh->zh_zoneorder = order_end;
184 zh->zh_free = (struct zh_freelist *)
185 ch_malloc(order * sizeof(struct zh_freelist));
186 zh->zh_seqno = (unsigned long *)ch_calloc(zh->zh_maxzones,
187 sizeof(unsigned long));
188 for (i = 0; i < order; i++) {
189 LDAP_LIST_INIT(&zh->zh_free[i]);
190 }
191 LDAP_LIST_INIT(&zh->zh_zopool);
192
193 for (i = 0; i < zh->zh_numzones; i++) {
194 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
195 MAP_PRIVATE, zh->zh_fd, 0);
196 zh->zh_maps[i] = (unsigned char **)
197 ch_malloc(order * sizeof(unsigned char *));
198 for (j = 0; j < order; j++) {
199 int shiftamt = order_start + 1 + j;
200 int nummaps = zh->zh_zonesize >> shiftamt;
201 assert(nummaps);
202 nummaps >>= 3;
203 if (!nummaps) nummaps = 1;
204 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
205 memset(zh->zh_maps[i][j], 0, nummaps);
206 }
207
208 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
209 slap_replenish_zopool(zh);
210 }
211 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
212 LDAP_LIST_REMOVE(zo, zo_link);
213 zo->zo_ptr = zh->zh_zones[i];
214 zo->zo_idx = i;
215 LDAP_LIST_INSERT_HEAD(&zh->zh_free[order-1], zo, zo_link);
216
217 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
218 slap_replenish_zopool(zh);
219 }
220 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
221 LDAP_LIST_REMOVE(zo, zo_link);
222 zo->zo_ptr = zh->zh_zones[i];
223 zo->zo_siz = zh->zh_zonesize;
224 zo->zo_idx = i;
225 ldap_avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, ldap_avl_dup_error);
226 ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]);
227 }
228
229 LDAP_STAILQ_INIT(&zh->zh_latency_history_queue);
230 ldap_pvt_thread_mutex_init(&zh->zh_mutex);
231 ldap_pvt_thread_rdwr_init(&zh->zh_lock);
232
233 return zh;
234 }
235
236 void *
slap_zn_malloc(ber_len_t size,void * ctx)237 slap_zn_malloc(
238 ber_len_t size,
239 void *ctx
240 )
241 {
242 struct zone_heap *zh = ctx;
243 ber_len_t size_shift;
244 int pad = 2*sizeof(int)-1, pad_shift;
245 int order = -1, order_start = -1;
246 struct zone_object *zo, *zo_new, *zo_left, *zo_right;
247 ber_len_t *ptr, *new;
248 int idx;
249 unsigned long diff;
250 int i, j, k;
251
252 Debug(LDAP_DEBUG_NONE,
253 "--> slap_zn_malloc: size=%d\n", size );
254
255 if (!zh) return ber_memalloc_x(size, NULL);
256
257 /* round up to doubleword boundary */
258 size += 2*sizeof(ber_len_t) + pad;
259 size &= ~pad;
260
261 size_shift = size - 1;
262 do {
263 order++;
264 } while (size_shift >>= 1);
265
266 pad_shift = pad - 1;
267 do {
268 order_start++;
269 } while (pad_shift >>= 1);
270
271 retry:
272
273 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
274 for (i = order; i <= zh->zh_zoneorder &&
275 LDAP_LIST_EMPTY(&zh->zh_free[i-order_start]); i++);
276
277 if (i == order) {
278 zo_new = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
279 LDAP_LIST_REMOVE(zo_new, zo_link);
280 ptr = zo_new->zo_ptr;
281 idx = zo_new->zo_idx;
282 diff = (unsigned long)((char*)ptr -
283 (char*)zh->zh_zones[idx]) >> (order + 1);
284 zh->zh_maps[idx][order-order_start][diff>>3] |= (1 << (diff & 0x7));
285 *ptr++ = zh->zh_seqno[idx];
286 *ptr++ = size - 2*sizeof(ber_len_t);
287 zo_new->zo_ptr = NULL;
288 zo_new->zo_idx = -1;
289 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_new, zo_link);
290 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
291 Debug(LDAP_DEBUG_NONE, "slap_zn_malloc: returning 0x%x, 0x%x\n",
292 ptr, (int)ptr>>(zh->zh_zoneorder+1) );
293 return((void*)ptr);
294 } else if (i <= zh->zh_zoneorder) {
295 for (j = i; j > order; j--) {
296 zo_left = LDAP_LIST_FIRST(&zh->zh_free[j-order_start]);
297 LDAP_LIST_REMOVE(zo_left, zo_link);
298 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
299 slap_replenish_zopool(zh);
300 }
301 zo_right = LDAP_LIST_FIRST(&zh->zh_zopool);
302 LDAP_LIST_REMOVE(zo_right, zo_link);
303 zo_right->zo_ptr = zo_left->zo_ptr + (1 << j);
304 zo_right->zo_idx = zo_left->zo_idx;
305 Debug(LDAP_DEBUG_NONE,
306 "slap_zn_malloc: split (left=0x%x, right=0x%x)\n",
307 zo_left->zo_ptr, zo_right->zo_ptr );
308 if (j == order + 1) {
309 ptr = zo_left->zo_ptr;
310 diff = (unsigned long)((char*)ptr -
311 (char*)zh->zh_zones[zo_left->zo_idx]) >> (order+1);
312 zh->zh_maps[zo_left->zo_idx][order-order_start][diff>>3] |=
313 (1 << (diff & 0x7));
314 *ptr++ = zh->zh_seqno[zo_left->zo_idx];
315 *ptr++ = size - 2*sizeof(ber_len_t);
316 LDAP_LIST_INSERT_HEAD(
317 &zh->zh_free[j-1-order_start], zo_right, zo_link);
318 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_left, zo_link);
319 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
320 Debug(LDAP_DEBUG_NONE,
321 "slap_zn_malloc: returning 0x%x, 0x%x\n",
322 ptr, (int)ptr>>(zh->zh_zoneorder+1) );
323 return((void*)ptr);
324 } else {
325 LDAP_LIST_INSERT_HEAD(
326 &zh->zh_free[j-1-order_start], zo_right, zo_link);
327 LDAP_LIST_INSERT_HEAD(
328 &zh->zh_free[j-1-order_start], zo_left, zo_link);
329 }
330 }
331 assert(0);
332 } else {
333
334 if ( zh->zh_maxzones < zh->zh_numzones + zh->zh_deltazones ) {
335 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
336 Debug( LDAP_DEBUG_TRACE,
337 "zn_malloc %lu: ch_malloc\n",
338 (long)size );
339 Debug(LDAP_DEBUG_NONE,
340 "slap_zn_malloc: returning 0x%x, 0x%x\n",
341 ptr, (int)ptr>>(zh->zh_zoneorder+1) );
342 return (void*)ch_malloc(size);
343 }
344
345 for (i = zh->zh_numzones; i < zh->zh_numzones+zh->zh_deltazones; i++) {
346 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
347 MAP_PRIVATE, zh->zh_fd, 0);
348 zh->zh_maps[i] = (unsigned char **)
349 ch_malloc((zh->zh_zoneorder - order_start + 1) *
350 sizeof(unsigned char *));
351 for (j = 0; j < zh->zh_zoneorder-order_start+1; j++) {
352 int shiftamt = order_start + 1 + j;
353 int nummaps = zh->zh_zonesize >> shiftamt;
354 assert(nummaps);
355 nummaps >>= 3;
356 if (!nummaps) nummaps = 1;
357 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
358 memset(zh->zh_maps[i][j], 0, nummaps);
359 }
360
361 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
362 slap_replenish_zopool(zh);
363 }
364 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
365 LDAP_LIST_REMOVE(zo, zo_link);
366 zo->zo_ptr = zh->zh_zones[i];
367 zo->zo_idx = i;
368 LDAP_LIST_INSERT_HEAD(&zh->
369 zh_free[zh->zh_zoneorder-order_start],zo,zo_link);
370
371 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
372 slap_replenish_zopool(zh);
373 }
374 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
375 LDAP_LIST_REMOVE(zo, zo_link);
376 zo->zo_ptr = zh->zh_zones[i];
377 zo->zo_siz = zh->zh_zonesize;
378 zo->zo_idx = i;
379 ldap_avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, ldap_avl_dup_error);
380 ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]);
381 }
382 zh->zh_numzones += zh->zh_deltazones;
383 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
384 goto retry;
385 }
386 }
387
388 void *
slap_zn_calloc(ber_len_t n,ber_len_t size,void * ctx)389 slap_zn_calloc( ber_len_t n, ber_len_t size, void *ctx )
390 {
391 void *new;
392
393 new = slap_zn_malloc( n*size, ctx );
394 if ( new ) {
395 memset( new, 0, n*size );
396 }
397 return new;
398 }
399
400 void *
slap_zn_realloc(void * ptr,ber_len_t size,void * ctx)401 slap_zn_realloc(void *ptr, ber_len_t size, void *ctx)
402 {
403 struct zone_heap *zh = ctx;
404 int pad = 2*sizeof(int)-1, pad_shift;
405 int order_start = -1, order = -1;
406 struct zone_object zoi, *zoo;
407 ber_len_t *p = (ber_len_t *)ptr, *new;
408 unsigned long diff;
409 int i;
410 void *newptr = NULL;
411 struct zone_heap *zone = NULL;
412
413 Debug(LDAP_DEBUG_NONE,
414 "--> slap_zn_realloc: ptr=0x%x, size=%d\n", ptr, size );
415
416 if (ptr == NULL)
417 return slap_zn_malloc(size, zh);
418
419 zoi.zo_ptr = p;
420 zoi.zo_idx = -1;
421
422 if (zh) {
423 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
424 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
425 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
426 }
427
428 /* Not our memory? */
429 if (!zoo) {
430 /* duplicate of realloc behavior, oh well */
431 new = ber_memrealloc_x(ptr, size, NULL);
432 if (new) {
433 return new;
434 }
435 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
436 (long) size );
437 assert(0);
438 exit( EXIT_FAILURE );
439 }
440
441 assert(zoo->zo_idx != -1);
442
443 zone = zh->zh_zones[zoo->zo_idx];
444
445 if (size == 0) {
446 slap_zn_free(ptr, zh);
447 return NULL;
448 }
449
450 newptr = slap_zn_malloc(size, zh);
451 if (size < p[-1]) {
452 AC_MEMCPY(newptr, ptr, size);
453 } else {
454 AC_MEMCPY(newptr, ptr, p[-1]);
455 }
456 slap_zn_free(ptr, zh);
457 return newptr;
458 }
459
460 void
slap_zn_free(void * ptr,void * ctx)461 slap_zn_free(void *ptr, void *ctx)
462 {
463 struct zone_heap *zh = ctx;
464 int size, size_shift, order_size;
465 int pad = 2*sizeof(int)-1, pad_shift;
466 ber_len_t *p = (ber_len_t *)ptr, *tmpp;
467 int order_start = -1, order = -1;
468 struct zone_object zoi, *zoo, *zo;
469 unsigned long diff;
470 int i, k, inserted = 0, idx;
471 struct zone_heap *zone = NULL;
472
473 zoi.zo_ptr = p;
474 zoi.zo_idx = -1;
475
476 Debug(LDAP_DEBUG_NONE, "--> slap_zn_free: ptr=0x%x\n", ptr );
477
478 if (zh) {
479 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
480 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
481 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
482 }
483
484 if (!zoo) {
485 ber_memfree_x(ptr, NULL);
486 } else {
487 idx = zoo->zo_idx;
488 assert(idx != -1);
489 zone = zh->zh_zones[idx];
490
491 size = *(--p);
492 size_shift = size + 2*sizeof(ber_len_t) - 1;
493 do {
494 order++;
495 } while (size_shift >>= 1);
496
497 pad_shift = pad - 1;
498 do {
499 order_start++;
500 } while (pad_shift >>= 1);
501
502 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
503 for (i = order, tmpp = p; i <= zh->zh_zoneorder; i++) {
504 order_size = 1 << (i+1);
505 diff = (unsigned long)((char*)tmpp - (char*)zone) >> (i+1);
506 zh->zh_maps[idx][i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
507 if (diff == ((diff>>1)<<1)) {
508 if (!(zh->zh_maps[idx][i-order_start][(diff+1)>>3] &
509 (1<<((diff+1)&0x7)))) {
510 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
511 while (zo) {
512 if ((char*)zo->zo_ptr == (char*)tmpp) {
513 LDAP_LIST_REMOVE( zo, zo_link );
514 } else if ((char*)zo->zo_ptr ==
515 (char*)tmpp + order_size) {
516 LDAP_LIST_REMOVE(zo, zo_link);
517 break;
518 }
519 zo = LDAP_LIST_NEXT(zo, zo_link);
520 }
521 if (zo) {
522 if (i < zh->zh_zoneorder) {
523 inserted = 1;
524 zo->zo_ptr = tmpp;
525 Debug(LDAP_DEBUG_NONE,
526 "slap_zn_free: merging 0x%x\n",
527 zo->zo_ptr );
528 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
529 zo, zo_link);
530 }
531 continue;
532 } else {
533 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
534 slap_replenish_zopool(zh);
535 }
536 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
537 LDAP_LIST_REMOVE(zo, zo_link);
538 zo->zo_ptr = tmpp;
539 zo->zo_idx = idx;
540 Debug(LDAP_DEBUG_NONE,
541 "slap_zn_free: merging 0x%x\n",
542 zo->zo_ptr );
543 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
544 zo, zo_link);
545 break;
546
547 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
548 "free object not found while bit is clear.\n" );
549 assert(zo != NULL);
550
551 }
552 } else {
553 if (!inserted) {
554 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
555 slap_replenish_zopool(zh);
556 }
557 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
558 LDAP_LIST_REMOVE(zo, zo_link);
559 zo->zo_ptr = tmpp;
560 zo->zo_idx = idx;
561 Debug(LDAP_DEBUG_NONE,
562 "slap_zn_free: merging 0x%x\n",
563 zo->zo_ptr );
564 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
565 zo, zo_link);
566 }
567 break;
568 }
569 } else {
570 if (!(zh->zh_maps[idx][i-order_start][(diff-1)>>3] &
571 (1<<((diff-1)&0x7)))) {
572 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
573 while (zo) {
574 if ((char*)zo->zo_ptr == (char*)tmpp) {
575 LDAP_LIST_REMOVE(zo, zo_link);
576 } else if ((char*)tmpp == zo->zo_ptr + order_size) {
577 LDAP_LIST_REMOVE(zo, zo_link);
578 tmpp = zo->zo_ptr;
579 break;
580 }
581 zo = LDAP_LIST_NEXT(zo, zo_link);
582 }
583 if (zo) {
584 if (i < zh->zh_zoneorder) {
585 inserted = 1;
586 Debug(LDAP_DEBUG_NONE,
587 "slap_zn_free: merging 0x%x\n",
588 zo->zo_ptr );
589 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
590 zo, zo_link);
591 continue;
592 }
593 } else {
594 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
595 slap_replenish_zopool(zh);
596 }
597 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
598 LDAP_LIST_REMOVE(zo, zo_link);
599 zo->zo_ptr = tmpp;
600 zo->zo_idx = idx;
601 Debug(LDAP_DEBUG_NONE,
602 "slap_zn_free: merging 0x%x\n",
603 zo->zo_ptr );
604 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
605 zo, zo_link);
606 break;
607
608 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
609 "free object not found while bit is clear.\n" );
610 assert(zo != NULL);
611
612 }
613 } else {
614 if ( !inserted ) {
615 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
616 slap_replenish_zopool(zh);
617 }
618 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
619 LDAP_LIST_REMOVE(zo, zo_link);
620 zo->zo_ptr = tmpp;
621 zo->zo_idx = idx;
622 Debug(LDAP_DEBUG_NONE,
623 "slap_zn_free: merging 0x%x\n",
624 zo->zo_ptr );
625 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
626 zo, zo_link);
627 }
628 break;
629 }
630 }
631 }
632 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
633 }
634 }
635
636 static int
slap_zone_cmp(const void * v1,const void * v2)637 slap_zone_cmp(const void *v1, const void *v2)
638 {
639 const struct zone_object *zo1 = v1;
640 const struct zone_object *zo2 = v2;
641 char *ptr1;
642 char *ptr2;
643 ber_len_t zpad;
644
645 zpad = zo2->zo_siz - 1;
646 ptr1 = (char*)(((unsigned long)zo1->zo_ptr + zpad) & ~zpad);
647 ptr2 = (char*)zo2->zo_ptr + ((char*)ptr1 - (char*)zo1->zo_ptr);
648 ptr2 = (char*)(((unsigned long)ptr2 + zpad) & ~zpad);
649 return (int)((char*)ptr1 - (char*)ptr2);
650 }
651
652 void *
slap_replenish_zopool(void * ctx)653 slap_replenish_zopool(
654 void *ctx
655 )
656 {
657 struct zone_heap* zh = ctx;
658 struct zone_object *zo_block;
659 int i;
660
661 zo_block = (struct zone_object *)ch_malloc(
662 SLAP_ZONE_ZOBLOCK * sizeof(struct zone_object));
663
664 if ( zo_block == NULL ) {
665 return NULL;
666 }
667
668 zo_block[0].zo_blockhead = 1;
669 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[0], zo_link);
670 for (i = 1; i < SLAP_ZONE_ZOBLOCK; i++) {
671 zo_block[i].zo_blockhead = 0;
672 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[i], zo_link );
673 }
674
675 return zo_block;
676 }
677
678 int
slap_zn_invalidate(void * ctx,void * ptr)679 slap_zn_invalidate(
680 void *ctx,
681 void *ptr
682 )
683 {
684 struct zone_heap* zh = ctx;
685 struct zone_object zoi, *zoo;
686 struct zone_heap *zone = NULL;
687 int seqno = *((ber_len_t*)ptr - 2);
688 int idx = -1, rc = 0;
689 int pad = 2*sizeof(int)-1, pad_shift;
690 int order_start = -1, i;
691 struct zone_object *zo;
692
693 pad_shift = pad - 1;
694 do {
695 order_start++;
696 } while (pad_shift >>= 1);
697
698 zoi.zo_ptr = ptr;
699 zoi.zo_idx = -1;
700
701 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
702 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
703
704 if (zoo) {
705 idx = zoo->zo_idx;
706 assert(idx != -1);
707 madvise(zh->zh_zones[idx], zh->zh_zonesize, MADV_DONTNEED);
708 for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) {
709 int shiftamt = order_start + 1 + i;
710 int nummaps = zh->zh_zonesize >> shiftamt;
711 assert(nummaps);
712 nummaps >>= 3;
713 if (!nummaps) nummaps = 1;
714 memset(zh->zh_maps[idx][i], 0, nummaps);
715 zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
716 while (zo) {
717 struct zone_object *zo_tmp = zo;
718 zo = LDAP_LIST_NEXT(zo, zo_link);
719 if (zo_tmp && zo_tmp->zo_idx == idx) {
720 LDAP_LIST_REMOVE(zo_tmp, zo_link);
721 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
722 }
723 }
724 }
725 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
726 slap_replenish_zopool(zh);
727 }
728 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
729 LDAP_LIST_REMOVE(zo, zo_link);
730 zo->zo_ptr = zh->zh_zones[idx];
731 zo->zo_idx = idx;
732 LDAP_LIST_INSERT_HEAD(&zh->zh_free[zh->zh_zoneorder-order_start],
733 zo, zo_link);
734 zh->zh_seqno[idx]++;
735 } else {
736 Debug(LDAP_DEBUG_NONE, "zone not found for (ctx=0x%x, ptr=0x%x) !\n",
737 ctx, ptr );
738 }
739
740 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
741 Debug(LDAP_DEBUG_NONE, "zone %d invalidate\n", idx );
742 return rc;
743 }
744
745 int
slap_zn_validate(void * ctx,void * ptr,int seqno)746 slap_zn_validate(
747 void *ctx,
748 void *ptr,
749 int seqno
750 )
751 {
752 struct zone_heap* zh = ctx;
753 struct zone_object zoi, *zoo;
754 struct zone_heap *zone = NULL;
755 int idx, rc = 0;
756
757 zoi.zo_ptr = ptr;
758 zoi.zo_idx = -1;
759
760 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
761
762 if (zoo) {
763 idx = zoo->zo_idx;
764 assert(idx != -1);
765 assert(seqno <= zh->zh_seqno[idx]);
766 rc = (seqno == zh->zh_seqno[idx]);
767 }
768
769 return rc;
770 }
771
slap_zh_rlock(void * ctx)772 int slap_zh_rlock(
773 void *ctx
774 )
775 {
776 struct zone_heap* zh = ctx;
777 ldap_pvt_thread_rdwr_rlock(&zh->zh_lock);
778 }
779
slap_zh_runlock(void * ctx)780 int slap_zh_runlock(
781 void *ctx
782 )
783 {
784 struct zone_heap* zh = ctx;
785 ldap_pvt_thread_rdwr_runlock(&zh->zh_lock);
786 }
787
slap_zh_wlock(void * ctx)788 int slap_zh_wlock(
789 void *ctx
790 )
791 {
792 struct zone_heap* zh = ctx;
793 ldap_pvt_thread_rdwr_wlock(&zh->zh_lock);
794 }
795
slap_zh_wunlock(void * ctx)796 int slap_zh_wunlock(
797 void *ctx
798 )
799 {
800 struct zone_heap* zh = ctx;
801 ldap_pvt_thread_rdwr_wunlock(&zh->zh_lock);
802 }
803
slap_zn_rlock(void * ctx,void * ptr)804 int slap_zn_rlock(
805 void *ctx,
806 void *ptr
807 )
808 {
809 struct zone_heap* zh = ctx;
810 struct zone_object zoi, *zoo;
811 struct zone_heap *zone = NULL;
812 int idx;
813
814 zoi.zo_ptr = ptr;
815 zoi.zo_idx = -1;
816
817 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
818 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
819 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
820
821 if (zoo) {
822 idx = zoo->zo_idx;
823 assert(idx != -1);
824 ldap_pvt_thread_rdwr_rlock(&zh->zh_znlock[idx]);
825 }
826 }
827
slap_zn_runlock(void * ctx,void * ptr)828 int slap_zn_runlock(
829 void *ctx,
830 void *ptr
831 )
832 {
833 struct zone_heap* zh = ctx;
834 struct zone_object zoi, *zoo;
835 struct zone_heap *zone = NULL;
836 int idx;
837
838 zoi.zo_ptr = ptr;
839 zoi.zo_idx = -1;
840
841 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
842 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
843 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
844
845 if (zoo) {
846 idx = zoo->zo_idx;
847 assert(idx != -1);
848 ldap_pvt_thread_rdwr_runlock(&zh->zh_znlock[idx]);
849 }
850 }
851
slap_zn_wlock(void * ctx,void * ptr)852 int slap_zn_wlock(
853 void *ctx,
854 void *ptr
855 )
856 {
857 struct zone_heap* zh = ctx;
858 struct zone_object zoi, *zoo;
859 struct zone_heap *zone = NULL;
860 int idx;
861
862 zoi.zo_ptr = ptr;
863 zoi.zo_idx = -1;
864
865 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
866 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
867 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
868
869 if (zoo) {
870 idx = zoo->zo_idx;
871 assert(idx != -1);
872 ldap_pvt_thread_rdwr_wlock(&zh->zh_znlock[idx]);
873 }
874 }
875
slap_zn_wunlock(void * ctx,void * ptr)876 int slap_zn_wunlock(
877 void *ctx,
878 void *ptr
879 )
880 {
881 struct zone_heap* zh = ctx;
882 struct zone_object zoi, *zoo;
883 struct zone_heap *zone = NULL;
884 int idx;
885
886 zoi.zo_ptr = ptr;
887 zoi.zo_idx = -1;
888
889 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
890 zoo = ldap_avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
891 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
892
893 if (zoo) {
894 idx = zoo->zo_idx;
895 assert(idx != -1);
896 ldap_pvt_thread_rdwr_wunlock(&zh->zh_znlock[idx]);
897 }
898 }
899
900 #define T_SEC_IN_USEC 1000000
901
902 static int
slap_timediff(struct timeval * tv_begin,struct timeval * tv_end)903 slap_timediff(struct timeval *tv_begin, struct timeval *tv_end)
904 {
905 uint64_t t_begin, t_end, t_diff;
906
907 t_begin = T_SEC_IN_USEC * tv_begin->tv_sec + tv_begin->tv_usec;
908 t_end = T_SEC_IN_USEC * tv_end->tv_sec + tv_end->tv_usec;
909 t_diff = t_end - t_begin;
910
911 if ( t_diff < 0 )
912 t_diff = 0;
913
914 return (int)t_diff;
915 }
916
917 void
slap_set_timing(struct timeval * tv_set)918 slap_set_timing(struct timeval *tv_set)
919 {
920 gettimeofday(tv_set, (struct timezone *)NULL);
921 }
922
923 int
slap_measure_timing(struct timeval * tv_set,struct timeval * tv_measure)924 slap_measure_timing(struct timeval *tv_set, struct timeval *tv_measure)
925 {
926 gettimeofday(tv_measure, (struct timezone *)NULL);
927 return(slap_timediff(tv_set, tv_measure));
928 }
929
930 #define EMA_WEIGHT 0.999000
931 #define SLAP_ZN_LATENCY_HISTORY_QLEN 500
932 int
slap_zn_latency_history(void * ctx,int ea_latency)933 slap_zn_latency_history(void* ctx, int ea_latency)
934 {
935 /* TODO: monitor /proc/stat (swap) as well */
936 struct zone_heap* zh = ctx;
937 double t_diff = 0.0;
938
939 zh->zh_ema_latency = (double)ea_latency * (1.0 - EMA_WEIGHT)
940 + zh->zh_ema_latency * EMA_WEIGHT;
941 if (!zh->zh_swapping && zh->zh_ema_samples++ % 100 == 99) {
942 struct zone_latency_history *zlh_entry;
943 zlh_entry = ch_calloc(1, sizeof(struct zone_latency_history));
944 zlh_entry->zlh_latency = zh->zh_ema_latency;
945 LDAP_STAILQ_INSERT_TAIL(
946 &zh->zh_latency_history_queue, zlh_entry, zlh_next);
947 zh->zh_latency_history_qlen++;
948 while (zh->zh_latency_history_qlen > SLAP_ZN_LATENCY_HISTORY_QLEN) {
949 struct zone_latency_history *zlh;
950 zlh = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue);
951 LDAP_STAILQ_REMOVE_HEAD(
952 &zh->zh_latency_history_queue, zlh_next);
953 zh->zh_latency_history_qlen--;
954 ch_free(zlh);
955 }
956 if (zh->zh_latency_history_qlen == SLAP_ZN_LATENCY_HISTORY_QLEN) {
957 struct zone_latency_history *zlh_first, *zlh_last;
958 zlh_first = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue);
959 zlh_last = LDAP_STAILQ_LAST(&zh->zh_latency_history_queue,
960 zone_latency_history, zlh_next);
961 t_diff = zlh_last->zlh_latency - zlh_first->zlh_latency;
962 }
963 if (t_diff >= 2000) {
964 zh->zh_latency_jump++;
965 } else {
966 zh->zh_latency_jump = 0;
967 }
968 if (zh->zh_latency_jump > 3) {
969 zh->zh_latency_jump = 0;
970 zh->zh_swapping = 1;
971 }
972 }
973 return zh->zh_swapping;
974 }
975 #endif /* SLAP_ZONE_ALLOC */
976