lib/bpf/strset.c

0001 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
0002 /* Copyright (c) 2021 Facebook */
0003 #include <stdint.h>
0004 #include <stdlib.h>
0005 #include <stdio.h>
0006 #include <errno.h>
0007 #include <linux/err.h>
0008 #include "hashmap.h"
0009 #include "libbpf_internal.h"
0010 #include "strset.h"
0011
0012 struct strset {
0013     void *strs_data;
0014     size_t strs_data_len;
0015     size_t strs_data_cap;
0016     size_t strs_data_max_len;
0017
0018     /* lookup index for each unique string in strings set */
0019     struct hashmap *strs_hash;
0020 };
0021
0022 static size_t strset_hash_fn(const void *key, void *ctx)
0023 {
0024     const struct strset *s = ctx;
0025     const char *str = s->strs_data + (long)key;
0026
0027     return str_hash(str);
0028 }
0029
0030 static bool strset_equal_fn(const void *key1, const void *key2, void *ctx)
0031 {
0032     const struct strset *s = ctx;
0033     const char *str1 = s->strs_data + (long)key1;
0034     const char *str2 = s->strs_data + (long)key2;
0035
0036     return strcmp(str1, str2) == 0;
0037 }
0038
0039 struct strset *strset__new(size_t max_data_sz, const char *init_data, size_t init_data_sz)
0040 {
0041     struct strset *set = calloc(1, sizeof(*set));
0042     struct hashmap *hash;
0043     int err = -ENOMEM;
0044
0045     if (!set)
0046         return ERR_PTR(-ENOMEM);
0047
0048     hash = hashmap__new(strset_hash_fn, strset_equal_fn, set);
0049     if (IS_ERR(hash))
0050         goto err_out;
0051
0052     set->strs_data_max_len = max_data_sz;
0053     set->strs_hash = hash;
0054
0055     if (init_data) {
0056         long off;
0057
0058         set->strs_data = malloc(init_data_sz);
0059         if (!set->strs_data)
0060             goto err_out;
0061
0062         memcpy(set->strs_data, init_data, init_data_sz);
0063         set->strs_data_len = init_data_sz;
0064         set->strs_data_cap = init_data_sz;
0065
0066         for (off = 0; off < set->strs_data_len; off += strlen(set->strs_data + off) + 1) {
0067             /* hashmap__add() returns EEXIST if string with the same
0068              * content already is in the hash map
0069              */
0070             err = hashmap__add(hash, (void *)off, (void *)off);
0071             if (err == -EEXIST)
0072                 continue; /* duplicate */
0073             if (err)
0074                 goto err_out;
0075         }
0076     }
0077
0078     return set;
0079 err_out:
0080     strset__free(set);
0081     return ERR_PTR(err);
0082 }
0083
0084 void strset__free(struct strset *set)
0085 {
0086     if (IS_ERR_OR_NULL(set))
0087         return;
0088
0089     hashmap__free(set->strs_hash);
0090     free(set->strs_data);
0091     free(set);
0092 }
0093
0094 size_t strset__data_size(const struct strset *set)
0095 {
0096     return set->strs_data_len;
0097 }
0098
0099 const char *strset__data(const struct strset *set)
0100 {
0101     return set->strs_data;
0102 }
0103
0104 static void *strset_add_str_mem(struct strset *set, size_t add_sz)
0105 {
0106     return libbpf_add_mem(&set->strs_data, &set->strs_data_cap, 1,
0107                   set->strs_data_len, set->strs_data_max_len, add_sz);
0108 }
0109
0110 /* Find string offset that corresponds to a given string *s*.
0111  * Returns:
0112  *   - >0 offset into string data, if string is found;
0113  *   - -ENOENT, if string is not in the string data;
0114  *   - <0, on any other error.
0115  */
0116 int strset__find_str(struct strset *set, const char *s)
0117 {
0118     long old_off, new_off, len;
0119     void *p;
0120
0121     /* see strset__add_str() for why we do this */
0122     len = strlen(s) + 1;
0123     p = strset_add_str_mem(set, len);
0124     if (!p)
0125         return -ENOMEM;
0126
0127     new_off = set->strs_data_len;
0128     memcpy(p, s, len);
0129
0130     if (hashmap__find(set->strs_hash, (void *)new_off, (void **)&old_off))
0131         return old_off;
0132
0133     return -ENOENT;
0134 }
0135
0136 /* Add a string s to the string data. If the string already exists, return its
0137  * offset within string data.
0138  * Returns:
0139  *   - > 0 offset into string data, on success;
0140  *   - < 0, on error.
0141  */
0142 int strset__add_str(struct strset *set, const char *s)
0143 {
0144     long old_off, new_off, len;
0145     void *p;
0146     int err;
0147
0148     /* Hashmap keys are always offsets within set->strs_data, so to even
0149      * look up some string from the "outside", we need to first append it
0150      * at the end, so that it can be addressed with an offset. Luckily,
0151      * until set->strs_data_len is incremented, that string is just a piece
0152      * of garbage for the rest of the code, so no harm, no foul. On the
0153      * other hand, if the string is unique, it's already appended and
0154      * ready to be used, only a simple set->strs_data_len increment away.
0155      */
0156     len = strlen(s) + 1;
0157     p = strset_add_str_mem(set, len);
0158     if (!p)
0159         return -ENOMEM;
0160
0161     new_off = set->strs_data_len;
0162     memcpy(p, s, len);
0163
0164     /* Now attempt to add the string, but only if the string with the same
0165      * contents doesn't exist already (HASHMAP_ADD strategy). If such
0166      * string exists, we'll get its offset in old_off (that's old_key).
0167      */
0168     err = hashmap__insert(set->strs_hash, (void *)new_off, (void *)new_off,
0169                   HASHMAP_ADD, (const void **)&old_off, NULL);
0170     if (err == -EEXIST)
0171         return old_off; /* duplicated string, return existing offset */
0172     if (err)
0173         return err;
0174
0175     set->strs_data_len += len; /* new unique string, adjust data length */
0176     return new_off;
0177 }