1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * util_ldap_cache_mgr.c: LDAP cache manager things
20 * Original code from auth_ldap module for Apache v1.3:
21 * Copyright 1998, 1999 Enbridge Pipelines Inc.
22 * Copyright 1999-2001 Dave Carrigan
26 #include "util_ldap.h"
27 #include "util_ldap_cache.h"
28 #include <apr_strings.h>
30 APLOG_USE_MODULE(ldap);
34 /* only here until strdup is gone */
37 /* here till malloc is gone */
40 static const unsigned long primes[] =
79 void util_ald_free(util_ald_cache_t *cache, const void *ptr)
81 #if APR_HAS_SHARED_MEMORY
82 if (cache->rmm_addr) {
84 /* Free in shared memory */
85 apr_rmm_free(cache->rmm_addr, apr_rmm_offset_get(cache->rmm_addr, (void *)ptr));
89 /* Cache shm is not used */
98 void *util_ald_alloc(util_ald_cache_t *cache, unsigned long size)
102 #if APR_HAS_SHARED_MEMORY
103 if (cache->rmm_addr) {
104 /* allocate from shared memory */
105 apr_rmm_off_t block = apr_rmm_calloc(cache->rmm_addr, size);
106 return block ? (void *)apr_rmm_addr_get(cache->rmm_addr, block) : NULL;
109 /* Cache shm is not used */
110 return (void *)calloc(sizeof(char), size);
113 return (void *)calloc(sizeof(char), size);
117 const char *util_ald_strdup(util_ald_cache_t *cache, const char *s)
119 #if APR_HAS_SHARED_MEMORY
120 if (cache->rmm_addr) {
121 /* allocate from shared memory */
122 apr_rmm_off_t block = apr_rmm_calloc(cache->rmm_addr, strlen(s)+1);
123 char *buf = block ? (char *)apr_rmm_addr_get(cache->rmm_addr, block) : NULL;
133 /* Cache shm is not used */
142 * Duplicate a subgroupList from one compare entry to another.
143 * Returns: ptr to a new copy of the subgroupList or NULL if allocation failed.
145 util_compare_subgroup_t *util_ald_sgl_dup(util_ald_cache_t *cache, util_compare_subgroup_t *sgl_in)
148 util_compare_subgroup_t *sgl_out = NULL;
154 sgl_out = (util_compare_subgroup_t *) util_ald_alloc(cache, sizeof(util_compare_subgroup_t));
156 sgl_out->subgroupDNs = util_ald_alloc(cache, sizeof(char *) * sgl_in->len);
157 if (sgl_out->subgroupDNs) {
158 for (i = 0; i < sgl_in->len; i++) {
159 sgl_out->subgroupDNs[i] = util_ald_strdup(cache, sgl_in->subgroupDNs[i]);
160 if (!sgl_out->subgroupDNs[i]) {
161 /* We ran out of SHM, delete the strings we allocated for the SGL */
162 for (i = (i - 1); i >= 0; i--) {
163 util_ald_free(cache, sgl_out->subgroupDNs[i]);
165 util_ald_free(cache, sgl_out->subgroupDNs);
166 util_ald_free(cache, sgl_out);
171 /* We were able to allocate new strings for all the subgroups */
172 if (sgl_out != NULL) {
173 sgl_out->len = sgl_in->len;
182 * Delete an entire subgroupList.
184 void util_ald_sgl_free(util_ald_cache_t *cache, util_compare_subgroup_t **sgl)
187 if (sgl == NULL || *sgl == NULL) {
191 for (i = 0; i < (*sgl)->len; i++) {
192 util_ald_free(cache, (*sgl)->subgroupDNs[i]);
194 util_ald_free(cache, *sgl);
198 * Computes the hash on a set of strings. The first argument is the number
199 * of strings to hash, the rest of the args are strings.
200 * Algorithm taken from glibc.
202 unsigned long util_ald_hash_string(int nstr, ...)
206 unsigned long h=0, g;
209 va_start(args, nstr);
210 for (i=0; i < nstr; ++i) {
211 str = va_arg(args, char *);
212 for (p = str; *p; ++p) {
214 if ( ( g = h & 0xf0000000 ) ) {
227 Purges a cache that has gotten full. We keep track of the time that we
228 added the entry that made the cache 3/4 full, then delete all entries
229 that were added before that time. It's pretty simplistic, but time to
230 purge is only O(n), which is more important.
232 void util_ald_cache_purge(util_ald_cache_t *cache)
235 util_cache_node_t *p, *q, **pp;
241 cache->last_purge = apr_time_now();
245 for (i=0; i < cache->size; ++i) {
246 pp = cache->nodes + i;
249 if (p->add_time < cache->marktime) {
251 (*cache->free)(cache, p->payload);
252 util_ald_free(cache, p);
265 cache->avg_purgetime =
266 ((t - cache->last_purge) + (cache->avg_purgetime * (cache->numpurges-1))) /
274 util_url_node_t *util_ald_create_caches(util_ldap_state_t *st, const char *url)
276 util_url_node_t curl, *newcurl = NULL;
277 util_ald_cache_t *search_cache;
278 util_ald_cache_t *compare_cache;
279 util_ald_cache_t *dn_compare_cache;
281 /* create the three caches */
282 search_cache = util_ald_create_cache(st,
283 st->search_cache_size,
284 util_ldap_search_node_hash,
285 util_ldap_search_node_compare,
286 util_ldap_search_node_copy,
287 util_ldap_search_node_free,
288 util_ldap_search_node_display);
289 compare_cache = util_ald_create_cache(st,
290 st->compare_cache_size,
291 util_ldap_compare_node_hash,
292 util_ldap_compare_node_compare,
293 util_ldap_compare_node_copy,
294 util_ldap_compare_node_free,
295 util_ldap_compare_node_display);
296 dn_compare_cache = util_ald_create_cache(st,
297 st->compare_cache_size,
298 util_ldap_dn_compare_node_hash,
299 util_ldap_dn_compare_node_compare,
300 util_ldap_dn_compare_node_copy,
301 util_ldap_dn_compare_node_free,
302 util_ldap_dn_compare_node_display);
304 /* check that all the caches initialised successfully */
305 if (search_cache && compare_cache && dn_compare_cache) {
307 /* The contents of this structure will be duplicated in shared
308 memory during the insert. So use stack memory rather than
309 pool memory to avoid a memory leak. */
310 memset (&curl, 0, sizeof(util_url_node_t));
312 curl.search_cache = search_cache;
313 curl.compare_cache = compare_cache;
314 curl.dn_compare_cache = dn_compare_cache;
316 newcurl = util_ald_cache_insert(st->util_ldap_cache, &curl);
324 util_ald_cache_t *util_ald_create_cache(util_ldap_state_t *st,
326 unsigned long (*hashfunc)(void *),
327 int (*comparefunc)(void *, void *),
328 void * (*copyfunc)(util_ald_cache_t *cache, void *),
329 void (*freefunc)(util_ald_cache_t *cache, void *),
330 void (*displayfunc)(request_rec *r, util_ald_cache_t *cache, void *))
332 util_ald_cache_t *cache;
338 #if APR_HAS_SHARED_MEMORY
339 if (!st->cache_rmm) {
343 apr_rmm_off_t block = apr_rmm_calloc(st->cache_rmm, sizeof(util_ald_cache_t));
344 cache = block ? (util_ald_cache_t *)apr_rmm_addr_get(st->cache_rmm, block) : NULL;
347 cache = (util_ald_cache_t *)calloc(sizeof(util_ald_cache_t), 1);
352 #if APR_HAS_SHARED_MEMORY
353 cache->rmm_addr = st->cache_rmm;
354 cache->shm_addr = st->cache_shm;
356 cache->maxentries = cache_size;
357 cache->numentries = 0;
358 cache->size = cache_size / 3;
359 if (cache->size < 64) cache->size = 64;
360 for (i = 0; primes[i] && primes[i] < cache->size; ++i) ;
361 cache->size = primes[i]? primes[i] : primes[i-1];
363 cache->nodes = (util_cache_node_t **)util_ald_alloc(cache, cache->size * sizeof(util_cache_node_t *));
365 util_ald_free(cache, cache);
369 for (i=0; i < cache->size; ++i)
370 cache->nodes[i] = NULL;
372 cache->hash = hashfunc;
373 cache->compare = comparefunc;
374 cache->copy = copyfunc;
375 cache->free = freefunc;
376 cache->display = displayfunc;
378 cache->fullmark = cache->maxentries / 4 * 3;
380 cache->avg_purgetime = 0.0;
381 cache->numpurges = 0;
382 cache->last_purge = 0;
393 void util_ald_destroy_cache(util_ald_cache_t *cache)
396 util_cache_node_t *p, *q;
401 for (i = 0; i < cache->size; ++i) {
406 (*cache->free)(cache, p->payload);
407 util_ald_free(cache, p);
411 util_ald_free(cache, cache->nodes);
412 util_ald_free(cache, cache);
415 void *util_ald_cache_fetch(util_ald_cache_t *cache, void *payload)
417 unsigned long hashval;
418 util_cache_node_t *p;
425 hashval = (*cache->hash)(payload) % cache->size;
427 for (p = cache->nodes[hashval];
428 p && !(*cache->compare)(p->payload, payload);
441 * Insert an item into the cache.
442 * *** Does not catch duplicates!!! ***
444 void *util_ald_cache_insert(util_ald_cache_t *cache, void *payload)
446 unsigned long hashval;
448 util_cache_node_t *node;
451 if (cache == NULL || payload == NULL) {
455 /* check if we are full - if so, try purge */
456 if (cache->numentries >= cache->maxentries) {
457 util_ald_cache_purge(cache);
458 if (cache->numentries >= cache->maxentries) {
459 /* if the purge was not effective, we leave now to avoid an overflow */
460 ap_log_error(APLOG_MARK, APLOG_ERR, 0, NULL,
461 "Purge of LDAP cache failed");
466 node = (util_cache_node_t *)util_ald_alloc(cache,
467 sizeof(util_cache_node_t));
470 * XXX: The cache management should be rewritten to work
471 * properly when LDAPSharedCacheSize is too small.
473 ap_log_error(APLOG_MARK, APLOG_WARNING, 0, NULL,
474 "LDAPSharedCacheSize is too small. Increase it or "
475 "reduce LDAPCacheEntries/LDAPOpCacheEntries!");
476 if (cache->numentries < cache->fullmark) {
478 * We have not even reached fullmark, trigger a complete purge.
479 * This is still better than not being able to add new entries
482 cache->marktime = apr_time_now();
484 util_ald_cache_purge(cache);
485 node = (util_cache_node_t *)util_ald_alloc(cache,
486 sizeof(util_cache_node_t));
488 ap_log_error(APLOG_MARK, APLOG_ERR, 0, NULL,
489 "Could not allocate memory for LDAP cache entry");
494 /* Take a copy of the payload before proceeeding. */
495 tmp_payload = (*cache->copy)(cache, payload);
496 if (tmp_payload == NULL) {
498 * XXX: The cache management should be rewritten to work
499 * properly when LDAPSharedCacheSize is too small.
501 ap_log_error(APLOG_MARK, APLOG_WARNING, 0, NULL,
502 "LDAPSharedCacheSize is too small. Increase it or "
503 "reduce LDAPCacheEntries/LDAPOpCacheEntries!");
504 if (cache->numentries < cache->fullmark) {
506 * We have not even reached fullmark, trigger a complete purge.
507 * This is still better than not being able to add new entries
510 cache->marktime = apr_time_now();
512 util_ald_cache_purge(cache);
513 tmp_payload = (*cache->copy)(cache, payload);
514 if (tmp_payload == NULL) {
515 ap_log_error(APLOG_MARK, APLOG_ERR, 0, NULL,
516 "Could not allocate memory for LDAP cache value");
517 util_ald_free(cache, node);
521 payload = tmp_payload;
523 /* populate the entry */
525 hashval = (*cache->hash)(payload) % cache->size;
526 node->add_time = apr_time_now();
527 node->payload = payload;
528 node->next = cache->nodes[hashval];
529 cache->nodes[hashval] = node;
531 /* if we reach the full mark, note the time we did so
532 * for the benefit of the purge function
534 if (++cache->numentries == cache->fullmark) {
535 cache->marktime=apr_time_now();
538 return node->payload;
541 void util_ald_cache_remove(util_ald_cache_t *cache, void *payload)
543 unsigned long hashval;
544 util_cache_node_t *p, *q;
550 hashval = (*cache->hash)(payload) % cache->size;
551 for (p = cache->nodes[hashval], q=NULL;
552 p && !(*cache->compare)(p->payload, payload);
557 /* If p is null, it means that we couldn't find the node, so just return */
562 /* We found the node, and it's the first in the list */
563 cache->nodes[hashval] = p->next;
566 /* We found the node and it's not the first in the list */
569 (*cache->free)(cache, p->payload);
570 util_ald_free(cache, p);
574 char *util_ald_cache_display_stats(request_rec *r, util_ald_cache_t *cache, char *name, char *id)
580 util_cache_node_t *n;
582 apr_pool_t *p = r->pool;
588 for (i=0; i < cache->size; ++i) {
589 if (cache->nodes[i] != NULL) {
591 for (n = cache->nodes[i];
592 n != NULL && n != n->next;
598 chainlen = nchains? (double)totchainlen / (double)nchains : 0;
601 buf2 = apr_psprintf(p,
602 "<a href=\"%s?%s\">%s</a>",
611 buf = apr_psprintf(p,
614 "<td align='right' nowrap>%lu (%.0f%% full)</td>"
615 "<td align='right'>%.1f</td>"
616 "<td align='right'>%lu/%lu</td>"
617 "<td align='right'>%.0f%%</td>"
618 "<td align='right'>%lu/%lu</td>",
621 (double)cache->numentries / (double)cache->maxentries * 100.0,
625 (cache->fetches > 0 ? (double)(cache->hits) / (double)(cache->fetches) * 100.0 : 100.0),
629 if (cache->numpurges) {
630 char str_ctime[APR_CTIME_LEN];
632 apr_ctime(str_ctime, cache->last_purge);
633 buf = apr_psprintf(p,
635 "<td align='right'>%lu</td>\n"
636 "<td align='right' nowrap>%s</td>\n",
642 buf = apr_psprintf(p,
643 "%s<td colspan='2' align='center'>(none)</td>\n",
647 buf = apr_psprintf(p, "%s<td align='right'>%.2gms</td>\n</tr>", buf, cache->avg_purgetime);
652 char *util_ald_cache_display(request_rec *r, util_ldap_state_t *st)
655 char *buf, *t1, *t2, *t3;
656 char *id1, *id2, *id3;
657 char *argfmt = "cache=%s&id=%d&off=%d";
658 char *scanfmt = "cache=%4s&id=%u&off=%u%1s";
659 apr_pool_t *pool = r->pool;
660 util_cache_node_t *p = NULL;
661 util_url_node_t *n = NULL;
663 util_ald_cache_t *util_ldap_cache = st->util_ldap_cache;
666 if (!util_ldap_cache) {
667 ap_rputs("<tr valign='top'><td nowrap colspan=7>Cache has not been enabled/initialised.</td></tr>", r);
671 if (r->args && strlen(r->args)) {
672 char cachetype[5], lint[2];
673 unsigned int id, off;
674 char date_str[APR_CTIME_LEN];
676 if ((3 == sscanf(r->args, scanfmt, cachetype, &id, &off, lint)) &&
677 (id < util_ldap_cache->size)) {
679 if ((p = util_ldap_cache->nodes[id]) != NULL) {
680 n = (util_url_node_t *)p->payload;
689 "<table border='0'>\n"
691 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Cache Name:</b></font></td>"
692 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%s (%s)</b></font></td>"
696 cachetype[0] == 'm'? "Main" :
697 (cachetype[0] == 's' ? "Search" :
698 (cachetype[0] == 'c' ? "Compares" : "DNCompares")));
700 switch (cachetype[0]) {
702 if (util_ldap_cache->marktime) {
703 apr_ctime(date_str, util_ldap_cache->marktime);
710 "<table border='0'>\n"
712 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Size:</b></font></td>"
713 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
716 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Max Entries:</b></font></td>"
717 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
720 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b># Entries:</b></font></td>"
721 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
724 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark:</b></font></td>"
725 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
728 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark Time:</b></font></td>"
729 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%s</b></font></td>"
732 util_ldap_cache->size,
733 util_ldap_cache->maxentries,
734 util_ldap_cache->numentries,
735 util_ldap_cache->fullmark,
739 "<table border='0'>\n"
740 "<tr bgcolor='#000000'>\n"
741 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>LDAP URL</b></font></td>"
742 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Size</b></font></td>"
743 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Max Entries</b></font></td>"
744 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b># Entries</b></font></td>"
745 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark</b></font></td>"
746 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark Time</b></font></td>"
749 for (i=0; i < util_ldap_cache->size; ++i) {
750 for (p = util_ldap_cache->nodes[i]; p != NULL; p = p->next) {
752 (*util_ldap_cache->display)(r, util_ldap_cache, p->payload);
755 ap_rputs("</table>\n</p>\n", r);
761 "<table border='0'>\n"
762 "<tr bgcolor='#000000'>\n"
763 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>LDAP Filter</b></font></td>"
764 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>User Name</b></font></td>"
765 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Last Bind</b></font></td>"
769 for (i=0; i < n->search_cache->size; ++i) {
770 for (p = n->search_cache->nodes[i]; p != NULL; p = p->next) {
772 (*n->search_cache->display)(r, n->search_cache, p->payload);
776 ap_rputs("</table>\n</p>\n", r);
780 "<table border='0'>\n"
781 "<tr bgcolor='#000000'>\n"
782 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>DN</b></font></td>"
783 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Attribute</b></font></td>"
784 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Value</b></font></td>"
785 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Last Compare</b></font></td>"
786 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Result</b></font></td>"
787 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Sub-groups?</b></font></td>"
788 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>S-G Checked?</b></font></td>"
792 for (i=0; i < n->compare_cache->size; ++i) {
793 for (p = n->compare_cache->nodes[i]; p != NULL; p = p->next) {
795 (*n->compare_cache->display)(r, n->compare_cache, p->payload);
799 ap_rputs("</table>\n</p>\n", r);
803 "<table border='0'>\n"
804 "<tr bgcolor='#000000'>\n"
805 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Require DN</b></font></td>"
806 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Actual DN</b></font></td>"
810 for (i=0; i < n->dn_compare_cache->size; ++i) {
811 for (p = n->dn_compare_cache->nodes[i]; p != NULL; p = p->next) {
813 (*n->dn_compare_cache->display)(r, n->dn_compare_cache, p->payload);
817 ap_rputs("</table>\n</p>\n", r);
830 "<table border='0'>\n"
831 "<tr bgcolor='#000000'>\n"
832 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Cache Name</b></font></td>"
833 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Entries</b></font></td>"
834 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Avg. Chain Len.</b></font></td>"
835 "<td colspan='2'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Hits</b></font></td>"
836 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Ins/Rem</b></font></td>"
837 "<td colspan='2'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Purges</b></font></td>"
838 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Avg Purge Time</b></font></td>"
843 id1 = apr_psprintf(pool, argfmt, "main", 0, 0);
844 buf = util_ald_cache_display_stats(r, st->util_ldap_cache, "LDAP URL Cache", id1);
846 for (i=0; i < util_ldap_cache->size; ++i) {
847 for (p = util_ldap_cache->nodes[i],j=0; p != NULL; p = p->next,j++) {
849 n = (util_url_node_t *)p->payload;
851 t1 = apr_psprintf(pool, "%s (Searches)", n->url);
852 t2 = apr_psprintf(pool, "%s (Compares)", n->url);
853 t3 = apr_psprintf(pool, "%s (DNCompares)", n->url);
854 id1 = apr_psprintf(pool, argfmt, "srch", i, j);
855 id2 = apr_psprintf(pool, argfmt, "cmpr", i, j);
856 id3 = apr_psprintf(pool, argfmt, "dncp", i, j);
858 buf = apr_psprintf(pool, "%s\n\n"
863 util_ald_cache_display_stats(r, n->search_cache, t1, id1),
864 util_ald_cache_display_stats(r, n->compare_cache, t2, id2),
865 util_ald_cache_display_stats(r, n->dn_compare_cache, t3, id3)
870 ap_rputs("</table>\n</p>\n", r);
876 #endif /* APR_HAS_LDAP */