/
githubmirror
/
audit-userspace
Обзор
Документация
Войти
/
githubmirror
/
audit-userspace
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
v4.2
auparse/lru.c
468 строк
10 KB
Steve Grubb
Fix LRU single-entry eviction
17 май 2026, 18:54
17 май 2026, 18:54
3b22894
Код
Авторство
О чём код?
/* * lru.c - LRU cache implementation * Copyright (c) 2016-17,20 Red Hat Inc. * All Rights Reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * Authors: * Steve Grubb <sgrubb@redhat.com> */ #include "config.h" #include <stdlib.h> #include <string.h> #include <syslog.h> #include "lru.h" #include "gcc-attributes.h" //#define DEBUG // Local declarations static void dequeue(Queue *queue); static unsigned int hash_name(const char *name); static void remove_hash_links(Queue *queue, QNode *node); static void free_qnode(Queue *queue, QNode *node); static void evict_lru(Queue *queue); static QNode *new_QNode(void) { QNode *temp = malloc(sizeof(QNode)); if (temp == NULL) return temp; temp->name = NULL; temp->uid = (uid_t)-1; temp->uses = 1; temp->prev = temp->next = NULL; return temp; } static Hash *create_hash(unsigned int hsize); static void destroy_hash(Hash *hash); #ifdef DEBUG static void dump_queue_stats(const Queue *q) { syslog(LOG_DEBUG, "%s queue size: %u", q->name, q->total); syslog(LOG_DEBUG, "%s slots in use: %u", q->name, q->count); syslog(LOG_DEBUG, "%s hits: %lu", q->name, q->hits); syslog(LOG_DEBUG, "%s misses: %lu", q->name, q->misses); syslog(LOG_DEBUG, "%s evictions: %lu", q->name, q->evictions); } #endif static Hash *create_hash(unsigned int hsize) { unsigned int i; Hash *hash = malloc(sizeof(Hash)); if (hash == NULL) return hash; hash->array = malloc(hsize * sizeof(QNode*)); if (hash->array == NULL) { free(hash); return NULL; } for (i = 0; i < hsize; i++) hash->array[i] = NULL; return hash; } static void destroy_hash(Hash *hash) { free(hash->array); free(hash); } /* * hash_name - djb2 string hash * @name: string to hash * * The djb2 algorithm offers a good balance between speed and * distribution for short account names, which makes it a reasonable * choice for indexing within the small LRU caches used here. */ static unsigned int hash_name(const char *name) { unsigned int h = 5381; unsigned char c; while (likely((c = *(const unsigned char *)name++))) h = ((h << 5) + h) + c; return h; } static Queue *create_queue(unsigned int qsize, const char *name) { Queue *queue = malloc(sizeof(Queue)); if (queue == NULL) return queue; // The queue is empty queue->count = 0; queue->hits = 0; queue->misses = 0; queue->evictions = 0; queue->front = queue->end = NULL; // Number of slots that can be stored in memory queue->total = qsize; queue->name = name; return queue; } static void destroy_queue(Queue *queue) { #ifdef DEBUG dump_queue_stats(queue); #endif // Some static analysis scanners try to flag this as a use after // free accessing queue->end. This is a false positive. It is freed. // However, static analysis apps are incapable of seeing that in // remove_node, end is updated to a prior node or cleared as part of // detaching the current end node. while (queue->count) dequeue(queue); free(queue); } /*static unsigned int are_all_slots_full(const Queue *queue) { return queue->count == queue->total; }*/ static unsigned int queue_is_empty(const Queue *queue) { return queue->end == NULL; } #ifdef DEBUG static void sanity_check_queue(Queue *q, const char *id) { unsigned int i; QNode *n; if (q == NULL) { syslog(LOG_DEBUG, "%s - q is NULL", id); abort(); } n = q->front; if (n == NULL) return; // Walk bottom to top i = 0; while (n->next) { if (n->next->prev != n) { syslog(LOG_DEBUG, "%s - corruption found %u", id, i); abort(); } if (i == q->count) { syslog(LOG_DEBUG, "%s - forward loop found %u", id, i); abort(); } i++; n = n->next; } // Walk top to bottom n = q->end; while (n->prev) { if (n->prev->next != n) { syslog(LOG_DEBUG, "%s - Corruption found %u", id, i); abort(); } if (i == 0) { syslog(LOG_DEBUG, "%s - backward loop found %u", id, i); abort(); } i--; n = n->prev; } } #else #define sanity_check_queue(a, b) do {} while(0) #endif static void insert_before(Queue *queue, QNode *node, QNode *new_node) { sanity_check_queue(queue, "1 insert_before"); if (queue == NULL || node == NULL || new_node == NULL) return; new_node->prev = node->prev; new_node->next = node; if (node->prev == NULL) queue->front = new_node; else node->prev->next = new_node; node->prev = new_node; sanity_check_queue(queue, "2 insert_before"); } static void insert_beginning(Queue *queue, QNode *new_node) { sanity_check_queue(queue, "1 insert_beginning"); if (queue == NULL || new_node == NULL) return; if (queue->front == NULL) { queue->front = new_node; queue->end = new_node; new_node->prev = NULL; new_node->next = NULL; } else insert_before(queue, queue->front, new_node); sanity_check_queue(queue, "2 insert_beginning"); } static void remove_node(Queue *queue, const QNode *node) { // If we are at the beginning sanity_check_queue(queue, "1 remove_node"); if (node->prev == NULL) { queue->front = node->next; if (queue->front) queue->front->prev = NULL; else queue->end = NULL; goto out; } else { if (node->prev->next != node) { #ifdef DEBUG syslog(LOG_ERR, "Linked list corruption detected %s", queue->name); #endif abort(); } node->prev->next = node->next; } // If we are at the end if (node->next == NULL) { queue->end = node->prev; if (queue->end) queue->end->next = NULL; } else { if (node->next->prev != node) { #ifdef DEBUG syslog(LOG_ERR, "Linked List corruption detected %s", queue->name); #endif abort(); } node->next->prev = node->prev; } out: sanity_check_queue(queue, "2 remove_node"); } static void remove_hash_links(Queue *queue, QNode *node) { unsigned int key; if (node->uid != (uid_t)-1) { key = node->uid % queue->total; if (queue->uid_hash->array[key] == node) queue->uid_hash->array[key] = NULL; } if (node->name) { key = hash_name(node->name) % queue->total; if (queue->name_hash->array[key] == node) queue->name_hash->array[key] = NULL; } } static void free_qnode(Queue *queue, QNode *node) { remove_hash_links(queue, node); remove_node(queue, node); free(node->name); free(node); queue->count--; } static void evict_lru(Queue *queue) { QNode *node; if (queue_is_empty(queue)) return; node = queue->end; free_qnode(queue, node); queue->evictions++; } // Remove from the end of the queue static void dequeue(Queue *queue) { QNode *node; if (queue_is_empty(queue)) return; node = queue->end; free_qnode(queue, node); } /* * check_lru_uid - find or create cache entry for a uid * @queue: cache queue to search * @uid: uid to locate * * Looks up the uid in the uid_hash table. On a hit the node is moved * to the front of the queue and returned. On a miss a new node is * allocated at the front of the queue, evicting the least recently * used entry if necessary. */ QNode *check_lru_uid(Queue *queue, uid_t uid) { QNode *node; unsigned int key; if (queue == NULL) return NULL; key = uid % queue->total; node = queue->uid_hash->array[key]; if (node && node->uid == uid) { if (node != queue->front) { remove_node(queue, node); insert_beginning(queue, node); } node->uses++; queue->hits++; return node; } queue->misses++; if (node) free_qnode(queue, node); else if (queue->count == queue->total) evict_lru(queue); node = new_QNode(); if (node == NULL) return NULL; node->uid = uid; insert_beginning(queue, node); queue->uid_hash->array[key] = node; queue->count++; return node; } /* * check_lru_name - find or create cache entry for a name * @queue: cache queue to search * @name: user name to locate * * Uses the djb2 hash to index into the name_hash table. On a hit the * node is moved to the front of the queue and returned. On a miss a * new node with the provided name is allocated and inserted at the * front, evicting the least recently used entry if the cache is full. */ QNode *check_lru_name(Queue *queue, const char *name) { QNode *node; unsigned int key; if (queue == NULL || name == NULL) return NULL; key = hash_name(name) % queue->total; node = queue->name_hash->array[key]; if (node && node->name && strcmp(node->name, name) == 0) { if (node != queue->front) { remove_node(queue, node); insert_beginning(queue, node); } node->uses++; queue->hits++; return node; } queue->misses++; if (node) free_qnode(queue, node); else if (queue->count == queue->total) evict_lru(queue); node = new_QNode(); if (node == NULL) return NULL; node->name = strdup(name); if (node->name == NULL) { free(node); return NULL; } insert_beginning(queue, node); queue->name_hash->array[key] = node; queue->count++; return node; } /* * init_lru - create a dual-key LRU cache * @qsize: maximum number of entries in the cache * @cleanup: optional callback to free user data * @name: identifier used in debug messages * * Allocates a queue with parallel hash tables: uid_hash is indexed by * simple modulo of the uid and name_hash uses the djb2 string hash. */ Queue *init_lru(unsigned int qsize, void (*cleanup)(void *), const char *name) { Queue *q = create_queue(qsize, name); if (q == NULL) return q; q->cleanup = cleanup; q->uid_hash = create_hash(qsize); q->name_hash = create_hash(qsize); if (q->uid_hash == NULL || q->name_hash == NULL) { if (q->uid_hash) destroy_hash(q->uid_hash); if (q->name_hash) destroy_hash(q->name_hash); free(q); return NULL; } return q; } void destroy_lru(Queue *queue) { Hash *uid_hash, *name_hash; if (queue == NULL) return; uid_hash = queue->uid_hash; name_hash = queue->name_hash; destroy_queue(queue); destroy_hash(uid_hash); destroy_hash(name_hash); }