178 lines · c
1// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)2/* Copyright (c) 2021 Facebook */3#include <stdint.h>4#include <stdlib.h>5#include <stdio.h>6#include <errno.h>7#include <linux/err.h>8#include "hashmap.h"9#include "libbpf_internal.h"10#include "strset.h"11 12struct strset {13 void *strs_data;14 size_t strs_data_len;15 size_t strs_data_cap;16 size_t strs_data_max_len;17 18 /* lookup index for each unique string in strings set */19 struct hashmap *strs_hash;20};21 22static size_t strset_hash_fn(long key, void *ctx)23{24 const struct strset *s = ctx;25 const char *str = s->strs_data + key;26 27 return str_hash(str);28}29 30static bool strset_equal_fn(long key1, long key2, void *ctx)31{32 const struct strset *s = ctx;33 const char *str1 = s->strs_data + key1;34 const char *str2 = s->strs_data + key2;35 36 return strcmp(str1, str2) == 0;37}38 39struct strset *strset__new(size_t max_data_sz, const char *init_data, size_t init_data_sz)40{41 struct strset *set = calloc(1, sizeof(*set));42 struct hashmap *hash;43 int err = -ENOMEM;44 45 if (!set)46 return ERR_PTR(-ENOMEM);47 48 hash = hashmap__new(strset_hash_fn, strset_equal_fn, set);49 if (IS_ERR(hash))50 goto err_out;51 52 set->strs_data_max_len = max_data_sz;53 set->strs_hash = hash;54 55 if (init_data) {56 long off;57 58 set->strs_data = malloc(init_data_sz);59 if (!set->strs_data)60 goto err_out;61 62 memcpy(set->strs_data, init_data, init_data_sz);63 set->strs_data_len = init_data_sz;64 set->strs_data_cap = init_data_sz;65 66 for (off = 0; off < set->strs_data_len; off += strlen(set->strs_data + off) + 1) {67 /* hashmap__add() returns EEXIST if string with the same68 * content already is in the hash map69 */70 err = hashmap__add(hash, off, off);71 if (err == -EEXIST)72 continue; /* duplicate */73 if (err)74 goto err_out;75 }76 }77 78 return set;79err_out:80 strset__free(set);81 return ERR_PTR(err);82}83 84void strset__free(struct strset *set)85{86 if (IS_ERR_OR_NULL(set))87 return;88 89 hashmap__free(set->strs_hash);90 free(set->strs_data);91 free(set);92}93 94size_t strset__data_size(const struct strset *set)95{96 return set->strs_data_len;97}98 99const char *strset__data(const struct strset *set)100{101 return set->strs_data;102}103 104static void *strset_add_str_mem(struct strset *set, size_t add_sz)105{106 return libbpf_add_mem(&set->strs_data, &set->strs_data_cap, 1,107 set->strs_data_len, set->strs_data_max_len, add_sz);108}109 110/* Find string offset that corresponds to a given string *s*.111 * Returns:112 * - >0 offset into string data, if string is found;113 * - -ENOENT, if string is not in the string data;114 * - <0, on any other error.115 */116int strset__find_str(struct strset *set, const char *s)117{118 long old_off, new_off, len;119 void *p;120 121 /* see strset__add_str() for why we do this */122 len = strlen(s) + 1;123 p = strset_add_str_mem(set, len);124 if (!p)125 return -ENOMEM;126 127 new_off = set->strs_data_len;128 memcpy(p, s, len);129 130 if (hashmap__find(set->strs_hash, new_off, &old_off))131 return old_off;132 133 return -ENOENT;134}135 136/* Add a string s to the string data. If the string already exists, return its137 * offset within string data.138 * Returns:139 * - > 0 offset into string data, on success;140 * - < 0, on error.141 */142int strset__add_str(struct strset *set, const char *s)143{144 long old_off, new_off, len;145 void *p;146 int err;147 148 /* Hashmap keys are always offsets within set->strs_data, so to even149 * look up some string from the "outside", we need to first append it150 * at the end, so that it can be addressed with an offset. Luckily,151 * until set->strs_data_len is incremented, that string is just a piece152 * of garbage for the rest of the code, so no harm, no foul. On the153 * other hand, if the string is unique, it's already appended and154 * ready to be used, only a simple set->strs_data_len increment away.155 */156 len = strlen(s) + 1;157 p = strset_add_str_mem(set, len);158 if (!p)159 return -ENOMEM;160 161 new_off = set->strs_data_len;162 memcpy(p, s, len);163 164 /* Now attempt to add the string, but only if the string with the same165 * contents doesn't exist already (HASHMAP_ADD strategy). If such166 * string exists, we'll get its offset in old_off (that's old_key).167 */168 err = hashmap__insert(set->strs_hash, new_off, new_off,169 HASHMAP_ADD, &old_off, NULL);170 if (err == -EEXIST)171 return old_off; /* duplicated string, return existing offset */172 if (err)173 return err;174 175 set->strs_data_len += len; /* new unique string, adjust data length */176 return new_off;177}178