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>
32 /* only here until strdup is gone */
35 /* here till malloc is gone */
38 static const unsigned long primes[] =
77 void util_ald_free(util_ald_cache_t *cache, const void *ptr)
79 #if APR_HAS_SHARED_MEMORY
80 if (cache->rmm_addr) {
82 /* Free in shared memory */
83 apr_rmm_free(cache->rmm_addr, apr_rmm_offset_get(cache->rmm_addr, (void *)ptr));
87 /* Cache shm is not used */
96 void *util_ald_alloc(util_ald_cache_t *cache, unsigned long size)
100 #if APR_HAS_SHARED_MEMORY
101 if (cache->rmm_addr) {
102 /* allocate from shared memory */
103 apr_rmm_off_t block = apr_rmm_calloc(cache->rmm_addr, size);
104 return block ? (void *)apr_rmm_addr_get(cache->rmm_addr, block) : NULL;
107 /* Cache shm is not used */
108 return (void *)calloc(sizeof(char), size);
111 return (void *)calloc(sizeof(char), size);
115 const char *util_ald_strdup(util_ald_cache_t *cache, const char *s)
117 #if APR_HAS_SHARED_MEMORY
118 if (cache->rmm_addr) {
119 /* allocate from shared memory */
120 apr_rmm_off_t block = apr_rmm_calloc(cache->rmm_addr, strlen(s)+1);
121 char *buf = block ? (char *)apr_rmm_addr_get(cache->rmm_addr, block) : NULL;
131 /* Cache shm is not used */
140 * Duplicate a subgroupList from one compare entry to another.
141 * Returns: ptr to a new copy of the subgroupList or NULL if allocation failed.
143 util_compare_subgroup_t *util_ald_sgl_dup(util_ald_cache_t *cache, util_compare_subgroup_t *sgl_in)
146 util_compare_subgroup_t *sgl_out = NULL;
152 sgl_out = (util_compare_subgroup_t *) util_ald_alloc(cache, sizeof(util_compare_subgroup_t));
154 sgl_out->subgroupDNs = util_ald_alloc(cache, sizeof(char *) * sgl_in->len);
155 if (sgl_out->subgroupDNs) {
156 for (i = 0; i < sgl_in->len; i++) {
157 sgl_out->subgroupDNs[i] = util_ald_strdup(cache, sgl_in->subgroupDNs[i]);
158 if (!sgl_out->subgroupDNs[i]) {
159 /* We ran out of SHM, delete the strings we allocated for the SGL */
160 for (i = (i - 1); i >= 0; i--) {
161 util_ald_free(cache, sgl_out->subgroupDNs[i]);
163 util_ald_free(cache, sgl_out->subgroupDNs);
164 util_ald_free(cache, sgl_out);
169 /* We were able to allocate new strings for all the subgroups */
170 if (sgl_out != NULL) {
171 sgl_out->len = sgl_in->len;
180 * Delete an entire subgroupList.
182 void util_ald_sgl_free(util_ald_cache_t *cache, util_compare_subgroup_t **sgl)
185 if (sgl == NULL || *sgl == NULL) {
189 for (i = 0; i < (*sgl)->len; i++) {
190 util_ald_free(cache, (*sgl)->subgroupDNs[i]);
192 util_ald_free(cache, *sgl);
196 * Computes the hash on a set of strings. The first argument is the number
197 * of strings to hash, the rest of the args are strings.
198 * Algorithm taken from glibc.
200 unsigned long util_ald_hash_string(int nstr, ...)
204 unsigned long h=0, g;
207 va_start(args, nstr);
208 for (i=0; i < nstr; ++i) {
209 str = va_arg(args, char *);
210 for (p = str; *p; ++p) {
212 if ( ( g = h & 0xf0000000 ) ) {
225 Purges a cache that has gotten full. We keep track of the time that we
226 added the entry that made the cache 3/4 full, then delete all entries
227 that were added before that time. It's pretty simplistic, but time to
228 purge is only O(n), which is more important.
230 void util_ald_cache_purge(util_ald_cache_t *cache)
233 util_cache_node_t *p, *q, **pp;
239 cache->last_purge = apr_time_now();
243 for (i=0; i < cache->size; ++i) {
244 pp = cache->nodes + i;
247 if (p->add_time < cache->marktime) {
249 (*cache->free)(cache, p->payload);
250 util_ald_free(cache, p);
263 cache->avg_purgetime =
264 ((t - cache->last_purge) + (cache->avg_purgetime * (cache->numpurges-1))) /
272 util_url_node_t *util_ald_create_caches(util_ldap_state_t *st, const char *url)
274 util_url_node_t curl, *newcurl = NULL;
275 util_ald_cache_t *search_cache;
276 util_ald_cache_t *compare_cache;
277 util_ald_cache_t *dn_compare_cache;
279 /* create the three caches */
280 search_cache = util_ald_create_cache(st,
281 st->search_cache_size,
282 util_ldap_search_node_hash,
283 util_ldap_search_node_compare,
284 util_ldap_search_node_copy,
285 util_ldap_search_node_free,
286 util_ldap_search_node_display);
287 compare_cache = util_ald_create_cache(st,
288 st->compare_cache_size,
289 util_ldap_compare_node_hash,
290 util_ldap_compare_node_compare,
291 util_ldap_compare_node_copy,
292 util_ldap_compare_node_free,
293 util_ldap_compare_node_display);
294 dn_compare_cache = util_ald_create_cache(st,
295 st->compare_cache_size,
296 util_ldap_dn_compare_node_hash,
297 util_ldap_dn_compare_node_compare,
298 util_ldap_dn_compare_node_copy,
299 util_ldap_dn_compare_node_free,
300 util_ldap_dn_compare_node_display);
302 /* check that all the caches initialised successfully */
303 if (search_cache && compare_cache && dn_compare_cache) {
305 /* The contents of this structure will be duplicated in shared
306 memory during the insert. So use stack memory rather than
307 pool memory to avoid a memory leak. */
308 memset (&curl, 0, sizeof(util_url_node_t));
310 curl.search_cache = search_cache;
311 curl.compare_cache = compare_cache;
312 curl.dn_compare_cache = dn_compare_cache;
314 newcurl = util_ald_cache_insert(st->util_ldap_cache, &curl);
322 util_ald_cache_t *util_ald_create_cache(util_ldap_state_t *st,
324 unsigned long (*hashfunc)(void *),
325 int (*comparefunc)(void *, void *),
326 void * (*copyfunc)(util_ald_cache_t *cache, void *),
327 void (*freefunc)(util_ald_cache_t *cache, void *),
328 void (*displayfunc)(request_rec *r, util_ald_cache_t *cache, void *))
330 util_ald_cache_t *cache;
336 #if APR_HAS_SHARED_MEMORY
337 if (!st->cache_rmm) {
341 apr_rmm_off_t block = apr_rmm_calloc(st->cache_rmm, sizeof(util_ald_cache_t));
342 cache = block ? (util_ald_cache_t *)apr_rmm_addr_get(st->cache_rmm, block) : NULL;
345 cache = (util_ald_cache_t *)calloc(sizeof(util_ald_cache_t), 1);
350 #if APR_HAS_SHARED_MEMORY
351 cache->rmm_addr = st->cache_rmm;
352 cache->shm_addr = st->cache_shm;
354 cache->maxentries = cache_size;
355 cache->numentries = 0;
356 cache->size = cache_size / 3;
357 if (cache->size < 64) cache->size = 64;
358 for (i = 0; primes[i] && primes[i] < cache->size; ++i) ;
359 cache->size = primes[i]? primes[i] : primes[i-1];
361 cache->nodes = (util_cache_node_t **)util_ald_alloc(cache, cache->size * sizeof(util_cache_node_t *));
363 util_ald_free(cache, cache);
367 for (i=0; i < cache->size; ++i)
368 cache->nodes[i] = NULL;
370 cache->hash = hashfunc;
371 cache->compare = comparefunc;
372 cache->copy = copyfunc;
373 cache->free = freefunc;
374 cache->display = displayfunc;
376 cache->fullmark = cache->maxentries / 4 * 3;
378 cache->avg_purgetime = 0.0;
379 cache->numpurges = 0;
380 cache->last_purge = 0;
391 void util_ald_destroy_cache(util_ald_cache_t *cache)
394 util_cache_node_t *p, *q;
399 for (i = 0; i < cache->size; ++i) {
404 (*cache->free)(cache, p->payload);
405 util_ald_free(cache, p);
409 util_ald_free(cache, cache->nodes);
410 util_ald_free(cache, cache);
413 void *util_ald_cache_fetch(util_ald_cache_t *cache, void *payload)
415 unsigned long hashval;
416 util_cache_node_t *p;
423 hashval = (*cache->hash)(payload) % cache->size;
425 for (p = cache->nodes[hashval];
426 p && !(*cache->compare)(p->payload, payload);
439 * Insert an item into the cache.
440 * *** Does not catch duplicates!!! ***
442 void *util_ald_cache_insert(util_ald_cache_t *cache, void *payload)
444 unsigned long hashval;
445 util_cache_node_t *node;
448 if (cache == NULL || payload == NULL) {
452 /* check if we are full - if so, try purge */
453 if (cache->numentries >= cache->maxentries) {
454 util_ald_cache_purge(cache);
455 if (cache->numentries >= cache->maxentries) {
456 /* if the purge was not effective, we leave now to avoid an overflow */
461 /* should be safe to add an entry */
462 if ((node = (util_cache_node_t *)util_ald_alloc(cache, sizeof(util_cache_node_t))) == NULL) {
466 /* Take a copy of the payload before proceeeding. */
467 payload = (*cache->copy)(cache, payload);
469 util_ald_free(cache, node);
473 /* populate the entry */
475 hashval = (*cache->hash)(payload) % cache->size;
476 node->add_time = apr_time_now();
477 node->payload = payload;
478 node->next = cache->nodes[hashval];
479 cache->nodes[hashval] = node;
481 /* if we reach the full mark, note the time we did so
482 * for the benefit of the purge function
484 if (++cache->numentries == cache->fullmark) {
485 cache->marktime=apr_time_now();
488 return node->payload;
491 void util_ald_cache_remove(util_ald_cache_t *cache, void *payload)
493 unsigned long hashval;
494 util_cache_node_t *p, *q;
500 hashval = (*cache->hash)(payload) % cache->size;
501 for (p = cache->nodes[hashval], q=NULL;
502 p && !(*cache->compare)(p->payload, payload);
507 /* If p is null, it means that we couldn't find the node, so just return */
512 /* We found the node, and it's the first in the list */
513 cache->nodes[hashval] = p->next;
516 /* We found the node and it's not the first in the list */
519 (*cache->free)(cache, p->payload);
520 util_ald_free(cache, p);
524 char *util_ald_cache_display_stats(request_rec *r, util_ald_cache_t *cache, char *name, char *id)
530 util_cache_node_t *n;
532 apr_pool_t *p = r->pool;
538 for (i=0; i < cache->size; ++i) {
539 if (cache->nodes[i] != NULL) {
541 for (n = cache->nodes[i];
542 n != NULL && n != n->next;
548 chainlen = nchains? (double)totchainlen / (double)nchains : 0;
551 buf2 = apr_psprintf(p,
552 "<a href=\"%s?%s\">%s</a>",
561 buf = apr_psprintf(p,
564 "<td align='right' nowrap>%lu (%.0f%% full)</td>"
565 "<td align='right'>%.1f</td>"
566 "<td align='right'>%lu/%lu</td>"
567 "<td align='right'>%.0f%%</td>"
568 "<td align='right'>%lu/%lu</td>",
571 (double)cache->numentries / (double)cache->maxentries * 100.0,
575 (cache->fetches > 0 ? (double)(cache->hits) / (double)(cache->fetches) * 100.0 : 100.0),
579 if (cache->numpurges) {
580 char str_ctime[APR_CTIME_LEN];
582 apr_ctime(str_ctime, cache->last_purge);
583 buf = apr_psprintf(p,
585 "<td align='right'>%lu</td>\n"
586 "<td align='right' nowrap>%s</td>\n",
592 buf = apr_psprintf(p,
593 "%s<td colspan='2' align='center'>(none)</td>\n",
597 buf = apr_psprintf(p, "%s<td align='right'>%.2gms</td>\n</tr>", buf, cache->avg_purgetime);
602 char *util_ald_cache_display(request_rec *r, util_ldap_state_t *st)
605 char *buf, *t1, *t2, *t3;
606 char *id1, *id2, *id3;
607 char *argfmt = "cache=%s&id=%d&off=%d";
608 char *scanfmt = "cache=%4s&id=%u&off=%u%1s";
609 apr_pool_t *pool = r->pool;
610 util_cache_node_t *p = NULL;
611 util_url_node_t *n = NULL;
613 util_ald_cache_t *util_ldap_cache = st->util_ldap_cache;
616 if (!util_ldap_cache) {
617 return "<tr valign='top'><td nowrap colspan=7>Cache has not been enabled/initialised.</td></tr>";
620 if (r->args && strlen(r->args)) {
621 char cachetype[5], lint[2];
622 unsigned int id, off;
623 char date_str[APR_CTIME_LEN];
625 if ((3 == sscanf(r->args, scanfmt, cachetype, &id, &off, lint)) &&
626 (id < util_ldap_cache->size)) {
628 if ((p = util_ldap_cache->nodes[id]) != NULL) {
629 n = (util_url_node_t *)p->payload;
638 "<table border='0'>\n"
640 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Cache Name:</b></font></td>"
641 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%s (%s)</b></font></td>"
645 cachetype[0] == 'm'? "Main" :
646 (cachetype[0] == 's' ? "Search" :
647 (cachetype[0] == 'c' ? "Compares" : "DNCompares")));
649 switch (cachetype[0]) {
651 if (util_ldap_cache->marktime) {
652 apr_ctime(date_str, util_ldap_cache->marktime);
659 "<table border='0'>\n"
661 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Size:</b></font></td>"
662 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
665 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Max Entries:</b></font></td>"
666 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
669 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b># Entries:</b></font></td>"
670 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
673 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark:</b></font></td>"
674 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%ld</b></font></td>"
677 "<td bgcolor='#000000'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark Time:</b></font></td>"
678 "<td bgcolor='#ffffff'><font size='-1' face='Arial,Helvetica' color='#000000'><b>%s</b></font></td>"
681 util_ldap_cache->size,
682 util_ldap_cache->maxentries,
683 util_ldap_cache->numentries,
684 util_ldap_cache->fullmark,
688 "<table border='0'>\n"
689 "<tr bgcolor='#000000'>\n"
690 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>LDAP URL</b></font></td>"
691 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Size</b></font></td>"
692 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Max Entries</b></font></td>"
693 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b># Entries</b></font></td>"
694 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark</b></font></td>"
695 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Full Mark Time</b></font></td>"
698 for (i=0; i < util_ldap_cache->size; ++i) {
699 for (p = util_ldap_cache->nodes[i]; p != NULL; p = p->next) {
701 (*util_ldap_cache->display)(r, util_ldap_cache, p->payload);
704 ap_rputs("</table>\n</p>\n", r);
710 "<table border='0'>\n"
711 "<tr bgcolor='#000000'>\n"
712 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>LDAP Filter</b></font></td>"
713 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>User Name</b></font></td>"
714 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Last Bind</b></font></td>"
718 for (i=0; i < n->search_cache->size; ++i) {
719 for (p = n->search_cache->nodes[i]; p != NULL; p = p->next) {
721 (*n->search_cache->display)(r, n->search_cache, p->payload);
725 ap_rputs("</table>\n</p>\n", r);
729 "<table border='0'>\n"
730 "<tr bgcolor='#000000'>\n"
731 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>DN</b></font></td>"
732 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Attribute</b></font></td>"
733 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Value</b></font></td>"
734 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Last Compare</b></font></td>"
735 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Result</b></font></td>"
736 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Sub-groups?</b></font></td>"
737 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>S-G Checked?</b></font></td>"
741 for (i=0; i < n->compare_cache->size; ++i) {
742 for (p = n->compare_cache->nodes[i]; p != NULL; p = p->next) {
744 (*n->compare_cache->display)(r, n->compare_cache, p->payload);
748 ap_rputs("</table>\n</p>\n", r);
752 "<table border='0'>\n"
753 "<tr bgcolor='#000000'>\n"
754 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Require DN</b></font></td>"
755 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Actual DN</b></font></td>"
759 for (i=0; i < n->dn_compare_cache->size; ++i) {
760 for (p = n->dn_compare_cache->nodes[i]; p != NULL; p = p->next) {
762 (*n->dn_compare_cache->display)(r, n->dn_compare_cache, p->payload);
766 ap_rputs("</table>\n</p>\n", r);
779 "<table border='0'>\n"
780 "<tr bgcolor='#000000'>\n"
781 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Cache Name</b></font></td>"
782 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Entries</b></font></td>"
783 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Avg. Chain Len.</b></font></td>"
784 "<td colspan='2'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Hits</b></font></td>"
785 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Ins/Rem</b></font></td>"
786 "<td colspan='2'><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Purges</b></font></td>"
787 "<td><font size='-1' face='Arial,Helvetica' color='#ffffff'><b>Avg Purge Time</b></font></td>"
792 id1 = apr_psprintf(pool, argfmt, "main", 0, 0);
793 buf = util_ald_cache_display_stats(r, st->util_ldap_cache, "LDAP URL Cache", id1);
795 for (i=0; i < util_ldap_cache->size; ++i) {
796 for (p = util_ldap_cache->nodes[i],j=0; p != NULL; p = p->next,j++) {
798 n = (util_url_node_t *)p->payload;
800 t1 = apr_psprintf(pool, "%s (Searches)", n->url);
801 t2 = apr_psprintf(pool, "%s (Compares)", n->url);
802 t3 = apr_psprintf(pool, "%s (DNCompares)", n->url);
803 id1 = apr_psprintf(pool, argfmt, "srch", i, j);
804 id2 = apr_psprintf(pool, argfmt, "cmpr", i, j);
805 id3 = apr_psprintf(pool, argfmt, "dncp", i, j);
807 buf = apr_psprintf(pool, "%s\n\n"
812 util_ald_cache_display_stats(r, n->search_cache, t1, id1),
813 util_ald_cache_display_stats(r, n->compare_cache, t2, id2),
814 util_ald_cache_display_stats(r, n->dn_compare_cache, t3, id3)
819 ap_rputs("</table>\n</p>\n", r);
825 #endif /* APR_HAS_LDAP */