drivers/net/wireguard/allowedips.c

111

static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits,

drivers/net/wireguard/allowedips.c

114

struct allowedips_node *node = trie, *found = NULL;

drivers/net/wireguard/allowedips.c

149

static bool node_placement(struct allowedips_node __rcu *trie, const u8 *key,

drivers/net/wireguard/allowedips.c

153

struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock));

drivers/net/wireguard/allowedips.c

181

static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key,

drivers/net/wireguard/allowedips.c

189

if (!rcu_access_pointer(*trie)) {

drivers/net/wireguard/allowedips.c

196

connect_node(trie, 2, node);

drivers/net/wireguard/allowedips.c

199

if (node_placement(*trie, key, cidr, bits, &node, lock)) {

drivers/net/wireguard/allowedips.c

213

down = rcu_dereference_protected(*trie, lockdep_is_held(lock));

drivers/net/wireguard/allowedips.c

228

connect_node(trie, 2, newnode);

drivers/net/wireguard/allowedips.c

246

connect_node(trie, 2, node);

drivers/net/wireguard/allowedips.c

283

static int remove(struct allowedips_node __rcu **trie, u8 bits, const u8 *key,

drivers/net/wireguard/allowedips.c

290

if (!rcu_access_pointer(*trie) || !node_placement(*trie, key, cidr, bits, &node, lock) ||

fs/unicode/mkutf8data.c

2709

utf8trie_t *trie;

fs/unicode/mkutf8data.c

2720

trie = utf8data + tree->index;

fs/unicode/mkutf8data.c

2722

offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;

fs/unicode/mkutf8data.c

2723

if (*trie & NEXTBYTE) {

fs/unicode/mkutf8data.c

2728

mask = 1 << (*trie & BITNUM);

fs/unicode/mkutf8data.c

2733

node = (*trie & RIGHTNODE);

fs/unicode/mkutf8data.c

2734

offset = trie[offlen];

fs/unicode/mkutf8data.c

2737

offset |= trie[offlen];

fs/unicode/mkutf8data.c

2739

trie += offset;

fs/unicode/mkutf8data.c

2740

} else if (*trie & RIGHTPATH) {

fs/unicode/mkutf8data.c

2742

node = (*trie & TRIENODE);

fs/unicode/mkutf8data.c

2743

trie++;

fs/unicode/mkutf8data.c

2752

node = (*trie & LEFTNODE);

fs/unicode/mkutf8data.c

2753

trie += offlen + 1;

fs/unicode/mkutf8data.c

2754

} else if (*trie & RIGHTPATH) {

fs/unicode/mkutf8data.c

2759

node = (*trie & TRIENODE);

fs/unicode/mkutf8data.c

2760

trie++;

fs/unicode/mkutf8data.c

2770

if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)

fs/unicode/mkutf8data.c

2771

trie = utf8hangul(s - 2, hangul);

fs/unicode/mkutf8data.c

2772

return trie;

fs/unicode/utf8-norm.c

306

utf8trie_t *trie = um->tables->utf8data + um->ntab[n]->offset;

fs/unicode/utf8-norm.c

317

offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;

fs/unicode/utf8-norm.c

318

if (*trie & NEXTBYTE) {

fs/unicode/utf8-norm.c

323

mask = 1 << (*trie & BITNUM);

fs/unicode/utf8-norm.c

328

node = (*trie & RIGHTNODE);

fs/unicode/utf8-norm.c

329

offset = trie[offlen];

fs/unicode/utf8-norm.c

332

offset |= trie[offlen];

fs/unicode/utf8-norm.c

334

trie += offset;

fs/unicode/utf8-norm.c

335

} else if (*trie & RIGHTPATH) {

fs/unicode/utf8-norm.c

337

node = (*trie & TRIENODE);

fs/unicode/utf8-norm.c

338

trie++;

fs/unicode/utf8-norm.c

347

node = (*trie & LEFTNODE);

fs/unicode/utf8-norm.c

348

trie += offlen + 1;

fs/unicode/utf8-norm.c

349

} else if (*trie & RIGHTPATH) {

fs/unicode/utf8-norm.c

354

node = (*trie & TRIENODE);

fs/unicode/utf8-norm.c

355

trie++;

fs/unicode/utf8-norm.c

365

if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)

fs/unicode/utf8-norm.c

366

trie = utf8hangul(s - 2, hangul);

fs/unicode/utf8-norm.c

367

return trie;

kernel/bpf/lpm_trie.c

168

size_t __longest_prefix_match(const struct lpm_trie *trie,

kernel/bpf/lpm_trie.c

183

if (trie->data_size >= 8) {

kernel/bpf/lpm_trie.c

196

while (trie->data_size >= i + 4) {

kernel/bpf/lpm_trie.c

208

if (trie->data_size >= i + 2) {

kernel/bpf/lpm_trie.c

220

if (trie->data_size >= i + 1) {

kernel/bpf/lpm_trie.c

230

static size_t longest_prefix_match(const struct lpm_trie *trie,

kernel/bpf/lpm_trie.c

234

return __longest_prefix_match(trie, node, key);

kernel/bpf/lpm_trie.c

240

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

244

if (key->prefixlen > trie->max_prefixlen)

kernel/bpf/lpm_trie.c

249

for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());

kernel/bpf/lpm_trie.c

258

matchlen = __longest_prefix_match(trie, node, key);

kernel/bpf/lpm_trie.c

259

if (matchlen == trie->max_prefixlen) {

kernel/bpf/lpm_trie.c

289

return found->data + trie->data_size;

kernel/bpf/lpm_trie.c

292

static struct lpm_trie_node *lpm_trie_node_alloc(struct lpm_trie *trie,

kernel/bpf/lpm_trie.c

297

node = bpf_mem_cache_alloc(&trie->ma);

kernel/bpf/lpm_trie.c

305

memcpy(node->data + trie->data_size, value,

kernel/bpf/lpm_trie.c

306

trie->map.value_size);

kernel/bpf/lpm_trie.c

311

static int trie_check_add_elem(struct lpm_trie *trie, u64 flags)

kernel/bpf/lpm_trie.c

315

if (trie->n_entries == trie->map.max_entries)

kernel/bpf/lpm_trie.c

317

trie->n_entries++;

kernel/bpf/lpm_trie.c

325

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

338

if (key->prefixlen > trie->max_prefixlen)

kernel/bpf/lpm_trie.c

342

new_node = lpm_trie_node_alloc(trie, value);

kernel/bpf/lpm_trie.c

346

ret = raw_res_spin_lock_irqsave(&trie->lock, irq_flags);

kernel/bpf/lpm_trie.c

353

memcpy(new_node->data, key->data, trie->data_size);

kernel/bpf/lpm_trie.c

360

slot = &trie->root;

kernel/bpf/lpm_trie.c

363

matchlen = longest_prefix_match(trie, node, key);

kernel/bpf/lpm_trie.c

377

ret = trie_check_add_elem(trie, flags);

kernel/bpf/lpm_trie.c

395

ret = trie_check_add_elem(trie, flags);

kernel/bpf/lpm_trie.c

409

ret = trie_check_add_elem(trie, flags);

kernel/bpf/lpm_trie.c

423

im_node = lpm_trie_node_alloc(trie, NULL);

kernel/bpf/lpm_trie.c

425

trie->n_entries--;

kernel/bpf/lpm_trie.c

432

memcpy(im_node->data, node->data, trie->data_size);

kernel/bpf/lpm_trie.c

447

raw_res_spin_unlock_irqrestore(&trie->lock, irq_flags);

kernel/bpf/lpm_trie.c

450

bpf_mem_cache_free(&trie->ma, new_node);

kernel/bpf/lpm_trie.c

451

bpf_mem_cache_free_rcu(&trie->ma, free_node);

kernel/bpf/lpm_trie.c

459

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

469

if (key->prefixlen > trie->max_prefixlen)

kernel/bpf/lpm_trie.c

472

ret = raw_res_spin_lock_irqsave(&trie->lock, irq_flags);

kernel/bpf/lpm_trie.c

482

trim = &trie->root;

kernel/bpf/lpm_trie.c

486

matchlen = longest_prefix_match(trie, node, key);

kernel/bpf/lpm_trie.c

505

trie->n_entries--;

kernel/bpf/lpm_trie.c

549

raw_res_spin_unlock_irqrestore(&trie->lock, irq_flags);

kernel/bpf/lpm_trie.c

551

bpf_mem_cache_free_rcu(&trie->ma, free_parent);

kernel/bpf/lpm_trie.c

552

bpf_mem_cache_free_rcu(&trie->ma, free_node);

kernel/bpf/lpm_trie.c

573

struct lpm_trie *trie;

kernel/bpf/lpm_trie.c

588

trie = bpf_map_area_alloc(sizeof(*trie), NUMA_NO_NODE);

kernel/bpf/lpm_trie.c

589

if (!trie)

kernel/bpf/lpm_trie.c

593

bpf_map_init_from_attr(&trie->map, attr);

kernel/bpf/lpm_trie.c

594

trie->data_size = attr->key_size -

kernel/bpf/lpm_trie.c

596

trie->max_prefixlen = trie->data_size * 8;

kernel/bpf/lpm_trie.c

598

raw_res_spin_lock_init(&trie->lock);

kernel/bpf/lpm_trie.c

601

leaf_size = sizeof(struct lpm_trie_node) + trie->data_size +

kernel/bpf/lpm_trie.c

602

trie->map.value_size;

kernel/bpf/lpm_trie.c

603

err = bpf_mem_alloc_init(&trie->ma, leaf_size, false);

kernel/bpf/lpm_trie.c

606

return &trie->map;

kernel/bpf/lpm_trie.c

609

bpf_map_area_free(trie);

kernel/bpf/lpm_trie.c

615

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

625

slot = &trie->root;

kernel/bpf/lpm_trie.c

652

bpf_mem_alloc_destroy(&trie->ma);

kernel/bpf/lpm_trie.c

653

bpf_map_area_free(trie);

kernel/bpf/lpm_trie.c

659

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

678

search_root = rcu_dereference(trie->root);

kernel/bpf/lpm_trie.c

683

if (!key || key->prefixlen > trie->max_prefixlen)

kernel/bpf/lpm_trie.c

687

trie->max_prefixlen + 1,

kernel/bpf/lpm_trie.c

695

matchlen = longest_prefix_match(trie, node, key);

kernel/bpf/lpm_trie.c

748

next_node->data, trie->data_size);

kernel/bpf/lpm_trie.c

766

struct lpm_trie *trie = container_of(map, struct lpm_trie, map);

kernel/bpf/lpm_trie.c

769

elem_size = sizeof(struct lpm_trie_node) + trie->data_size +

kernel/bpf/lpm_trie.c

770

trie->map.value_size;

kernel/bpf/lpm_trie.c

771

return elem_size * READ_ONCE(trie->n_entries);

net/ipv4/fib_trie.c

1017

struct trie *t;

net/ipv4/fib_trie.c

1023

t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

1098

static void trie_rebalance(struct trie *t, struct key_vector *tn)

net/ipv4/fib_trie.c

1104

static int fib_insert_node(struct trie *t, struct key_vector *tp,

net/ipv4/fib_trie.c

1154

static int fib_insert_alias(struct trie *t, struct key_vector *tp,

net/ipv4/fib_trie.c

1190

static void fib_remove_alias(struct trie *t, struct key_vector *tp,

net/ipv4/fib_trie.c

1197

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

1423

struct trie *t = (struct trie *) tb->tb_data;

net/ipv4/fib_trie.c

1626

static void fib_remove_alias(struct trie *t, struct key_vector *tp,

net/ipv4/fib_trie.c

1691

struct trie *t = (struct trie *) tb->tb_data;

net/ipv4/fib_trie.c

174

static struct key_vector *resize(struct trie *t, struct key_vector *tn);

net/ipv4/fib_trie.c

1816

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

1874

struct trie *ot = (struct trie *)oldtb->tb_data;

net/ipv4/fib_trie.c

1878

struct trie *lt;

net/ipv4/fib_trie.c

1888

lt = (struct trie *)local_tb->tb_data;

net/ipv4/fib_trie.c

1933

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2002

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2093

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2188

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2229

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2332

struct trie *t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

2387

struct trie *t;

net/ipv4/fib_trie.c

2391

sz += sizeof(struct trie);

net/ipv4/fib_trie.c

2404

t = (struct trie *) tb->tb_data;

net/ipv4/fib_trie.c

2472

struct trie *t)

net/ipv4/fib_trie.c

2497

static void trie_collect_stats(struct trie *t, struct trie_stat *s)

net/ipv4/fib_trie.c

2626

struct trie *t = (struct trie *) tb->tb_data;

net/ipv4/fib_trie.c

2662

(struct trie *) tb->tb_data);

net/ipv4/fib_trie.c

2700

n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);

net/ipv4/fib_trie.c

2709

n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);

net/ipv4/fib_trie.c

2868

struct trie *t;

net/ipv4/fib_trie.c

2877

t = (struct trie *)tb->tb_data;

net/ipv4/fib_trie.c

502

static struct key_vector *replace(struct trie *t,

net/ipv4/fib_trie.c

531

static struct key_vector *inflate(struct trie *t,

net/ipv4/fib_trie.c

627

static struct key_vector *halve(struct trie *t,

net/ipv4/fib_trie.c

682

static struct key_vector *collapse(struct trie *t,

net/ipv4/fib_trie.c

842

static struct key_vector *resize(struct trie *t, struct key_vector *tn)

net/ipv4/fib_trie.c

930

static struct key_vector *fib_find_node(struct trie *t,