security/selinux/ss/hashtab.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /*
   3  * A hash table (hashtab) maintains associations between
   4  * key values and datum values.  The type of the key values
   5  * and the type of the datum values is arbitrary.  The
   6  * functions for hash computation and key comparison are
   7  * provided by the creator of the table.
   8  *
   9  * Author : Stephen Smalley, <stephen.smalley.work@gmail.com>
  10  */
  11 #ifndef _SS_HASHTAB_H_
  12 #define _SS_HASHTAB_H_
  13
  14 #include <linux/types.h>
  15 #include <linux/errno.h>
  16 #include <linux/sched.h>
  17
  18 #define HASHTAB_MAX_NODES       U32_MAX
  19
  20 struct hashtab_key_params {
  21         u32 (*hash)(const void *key);   /* hash function */
  22         int (*cmp)(const void *key1, const void *key2);
  23                                         /* key comparison function */
  24 };
  25
  26 struct hashtab_node {
  27         void *key;
  28         void *datum;
  29         struct hashtab_node *next;
  30 };
  31
  32 struct hashtab {
  33         struct hashtab_node **htable;   /* hash table */
  34         u32 size;                       /* number of slots in hash table */
  35         u32 nel;                        /* number of elements in hash table */
  36 };
  37
  38 struct hashtab_info {
  39         u32 slots_used;
  40         u32 max_chain_len;
  41         u64 chain2_len_sum;
  42 };
  43
  44 /*
  45  * Initializes a new hash table with the specified characteristics.
  46  *
  47  * Returns -ENOMEM if insufficient space is available or 0 otherwise.
  48  */
  49 int hashtab_init(struct hashtab *h, u32 nel_hint);
  50
  51 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
  52                      void *key, void *datum);
  53
  54 /*
  55  * Inserts the specified (key, datum) pair into the specified hash table.
  56  *
  57  * Returns -ENOMEM on memory allocation error,
  58  * -EEXIST if there is already an entry with the same key,
  59  * -EINVAL for general errors or
  60   0 otherwise.
  61  */
  62 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
  63                                  struct hashtab_key_params key_params)
  64 {
  65         u32 hvalue;
  66         struct hashtab_node *prev, *cur;
  67
  68         cond_resched();
  69
  70         if (!h->size || h->nel == HASHTAB_MAX_NODES)
  71                 return -EINVAL;
  72
  73         hvalue = key_params.hash(key) & (h->size - 1);
  74         prev = NULL;
  75         cur = h->htable[hvalue];
  76         while (cur) {
  77                 int cmp = key_params.cmp(key, cur->key);
  78
  79                 if (cmp == 0)
  80                         return -EEXIST;
  81                 if (cmp < 0)
  82                         break;
  83                 prev = cur;
  84                 cur = cur->next;
  85         }
  86
  87         return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
  88                                 key, datum);
  89 }
  90
  91 /*
  92  * Searches for the entry with the specified key in the hash table.
  93  *
  94  * Returns NULL if no entry has the specified key or
  95  * the datum of the entry otherwise.
  96  */
  97 static inline void *hashtab_search(struct hashtab *h, const void *key,
  98                                    struct hashtab_key_params key_params)
  99 {
 100         u32 hvalue;
 101         struct hashtab_node *cur;
 102
 103         if (!h->size)
 104                 return NULL;
 105
 106         hvalue = key_params.hash(key) & (h->size - 1);
 107         cur = h->htable[hvalue];
 108         while (cur) {
 109                 int cmp = key_params.cmp(key, cur->key);
 110
 111                 if (cmp == 0)
 112                         return cur->datum;
 113                 if (cmp < 0)
 114                         break;
 115                 cur = cur->next;
 116         }
 117         return NULL;
 118 }
 119
 120 /*
 121  * Destroys the specified hash table.
 122  */
 123 void hashtab_destroy(struct hashtab *h);
 124
 125 /*
 126  * Applies the specified apply function to (key,datum,args)
 127  * for each entry in the specified hash table.
 128  *
 129  * The order in which the function is applied to the entries
 130  * is dependent upon the internal structure of the hash table.
 131  *
 132  * If apply returns a non-zero status, then hashtab_map will cease
 133  * iterating through the hash table and will propagate the error
 134  * return to its caller.
 135  */
 136 int hashtab_map(struct hashtab *h,
 137                 int (*apply)(void *k, void *d, void *args),
 138                 void *args);
 139
 140 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
 141                 int (*copy)(struct hashtab_node *new,
 142                         struct hashtab_node *orig, void *args),
 143                 int (*destroy)(void *k, void *d, void *args),
 144                 void *args);
 145
 146 #ifdef CONFIG_SECURITY_SELINUX_DEBUG
 147 /* Fill info with some hash table statistics */
 148 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
 149 #else
 150 static inline void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 151 {
 152 }
 153 #endif
 154
 155 #endif  /* _SS_HASHTAB_H */