1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * tracing_map - lock-free map for tracing
   4 *
   5 * Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com>
   6 *
   7 * tracing_map implementation inspired by lock-free map algorithms
   8 * originated by Dr. Cliff Click:
   9 *
  10 * http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable
  11 * http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
  12 */
  13
  14#include <linux/vmalloc.h>
  15#include <linux/jhash.h>
  16#include <linux/slab.h>
  17#include <linux/sort.h>
  18#include <linux/kmemleak.h>
  19
  20#include "tracing_map.h"
  21#include "trace.h"
  22
  23/*
  24 * NOTE: For a detailed description of the data structures used by
  25 * these functions (such as tracing_map_elt) please see the overview
  26 * of tracing_map data structures at the beginning of tracing_map.h.
  27 */
  28
  29/**
  30 * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
  31 * @elt: The tracing_map_elt
  32 * @i: The index of the given sum associated with the tracing_map_elt
  33 * @n: The value to add to the sum
  34 *
  35 * Add n to sum i associated with the specified tracing_map_elt
  36 * instance.  The index i is the index returned by the call to
  37 * tracing_map_add_sum_field() when the tracing map was set up.
  38 */
  39void tracing_map_update_sum(struct tracing_map_elt *elt, unsigned int i, u64 n)
  40{
  41	atomic64_add(n, &elt->fields[i].sum);
  42}
  43
  44/**
  45 * tracing_map_read_sum - Return the value of a tracing_map_elt's sum field
  46 * @elt: The tracing_map_elt
  47 * @i: The index of the given sum associated with the tracing_map_elt
  48 *
  49 * Retrieve the value of the sum i associated with the specified
  50 * tracing_map_elt instance.  The index i is the index returned by the
  51 * call to tracing_map_add_sum_field() when the tracing map was set
  52 * up.
  53 *
  54 * Return: The sum associated with field i for elt.
  55 */
  56u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i)
  57{
  58	return (u64)atomic64_read(&elt->fields[i].sum);
  59}
  60
  61/**
  62 * tracing_map_set_var - Assign a tracing_map_elt's variable field
  63 * @elt: The tracing_map_elt
  64 * @i: The index of the given variable associated with the tracing_map_elt
  65 * @n: The value to assign
  66 *
  67 * Assign n to variable i associated with the specified tracing_map_elt
  68 * instance.  The index i is the index returned by the call to
  69 * tracing_map_add_var() when the tracing map was set up.
  70 */
  71void tracing_map_set_var(struct tracing_map_elt *elt, unsigned int i, u64 n)
  72{
  73	atomic64_set(&elt->vars[i], n);
  74	elt->var_set[i] = true;
  75}
  76
  77/**
  78 * tracing_map_var_set - Return whether or not a variable has been set
  79 * @elt: The tracing_map_elt
  80 * @i: The index of the given variable associated with the tracing_map_elt
  81 *
  82 * Return true if the variable has been set, false otherwise.  The
  83 * index i is the index returned by the call to tracing_map_add_var()
  84 * when the tracing map was set up.
  85 */
  86bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i)
  87{
  88	return elt->var_set[i];
  89}
  90
  91/**
  92 * tracing_map_read_var - Return the value of a tracing_map_elt's variable field
  93 * @elt: The tracing_map_elt
  94 * @i: The index of the given variable associated with the tracing_map_elt
  95 *
  96 * Retrieve the value of the variable i associated with the specified
  97 * tracing_map_elt instance.  The index i is the index returned by the
  98 * call to tracing_map_add_var() when the tracing map was set
  99 * up.
 100 *
 101 * Return: The variable value associated with field i for elt.
 102 */
 103u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i)
 104{
 105	return (u64)atomic64_read(&elt->vars[i]);
 106}
 107
 108/**
 109 * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field
 110 * @elt: The tracing_map_elt
 111 * @i: The index of the given variable associated with the tracing_map_elt
 112 *
 113 * Retrieve the value of the variable i associated with the specified
 114 * tracing_map_elt instance, and reset the variable to the 'not set'
 115 * state.  The index i is the index returned by the call to
 116 * tracing_map_add_var() when the tracing map was set up.  The reset
 117 * essentially makes the variable a read-once variable if it's only
 118 * accessed using this function.
 119 *
 120 * Return: The variable value associated with field i for elt.
 121 */
 122u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i)
 123{
 124	elt->var_set[i] = false;
 125	return (u64)atomic64_read(&elt->vars[i]);
 126}
 127
 128int tracing_map_cmp_string(void *val_a, void *val_b)
 129{
 130	char *a = val_a;
 131	char *b = val_b;
 132
 133	return strcmp(a, b);
 134}
 135
 136int tracing_map_cmp_none(void *val_a, void *val_b)
 137{
 138	return 0;
 139}
 140
 141static int tracing_map_cmp_atomic64(void *val_a, void *val_b)
 142{
 143	u64 a = atomic64_read((atomic64_t *)val_a);
 144	u64 b = atomic64_read((atomic64_t *)val_b);
 145
 146	return (a > b) ? 1 : ((a < b) ? -1 : 0);
 147}
 148
 149#define DEFINE_TRACING_MAP_CMP_FN(type)					\
 150static int tracing_map_cmp_##type(void *val_a, void *val_b)		\
 151{									\
 152	type a = (type)(*(u64 *)val_a);					\
 153	type b = (type)(*(u64 *)val_b);					\
 154									\
 155	return (a > b) ? 1 : ((a < b) ? -1 : 0);			\
 156}
 157
 158DEFINE_TRACING_MAP_CMP_FN(s64);
 159DEFINE_TRACING_MAP_CMP_FN(u64);
 160DEFINE_TRACING_MAP_CMP_FN(s32);
 161DEFINE_TRACING_MAP_CMP_FN(u32);
 162DEFINE_TRACING_MAP_CMP_FN(s16);
 163DEFINE_TRACING_MAP_CMP_FN(u16);
 164DEFINE_TRACING_MAP_CMP_FN(s8);
 165DEFINE_TRACING_MAP_CMP_FN(u8);
 166
 167tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size,
 168					 int field_is_signed)
 169{
 170	tracing_map_cmp_fn_t fn = tracing_map_cmp_none;
 171
 172	switch (field_size) {
 173	case 8:
 174		if (field_is_signed)
 175			fn = tracing_map_cmp_s64;
 176		else
 177			fn = tracing_map_cmp_u64;
 178		break;
 179	case 4:
 180		if (field_is_signed)
 181			fn = tracing_map_cmp_s32;
 182		else
 183			fn = tracing_map_cmp_u32;
 184		break;
 185	case 2:
 186		if (field_is_signed)
 187			fn = tracing_map_cmp_s16;
 188		else
 189			fn = tracing_map_cmp_u16;
 190		break;
 191	case 1:
 192		if (field_is_signed)
 193			fn = tracing_map_cmp_s8;
 194		else
 195			fn = tracing_map_cmp_u8;
 196		break;
 197	}
 198
 199	return fn;
 200}
 201
 202static int tracing_map_add_field(struct tracing_map *map,
 203				 tracing_map_cmp_fn_t cmp_fn)
 204{
 205	int ret = -EINVAL;
 206
 207	if (map->n_fields < TRACING_MAP_FIELDS_MAX) {
 208		ret = map->n_fields;
 209		map->fields[map->n_fields++].cmp_fn = cmp_fn;
 210	}
 211
 212	return ret;
 213}
 214
 215/**
 216 * tracing_map_add_sum_field - Add a field describing a tracing_map sum
 217 * @map: The tracing_map
 218 *
 219 * Add a sum field to the key and return the index identifying it in
 220 * the map and associated tracing_map_elts.  This is the index used
 221 * for instance to update a sum for a particular tracing_map_elt using
 222 * tracing_map_update_sum() or reading it via tracing_map_read_sum().
 223 *
 224 * Return: The index identifying the field in the map and associated
 225 * tracing_map_elts, or -EINVAL on error.
 226 */
 227int tracing_map_add_sum_field(struct tracing_map *map)
 228{
 229	return tracing_map_add_field(map, tracing_map_cmp_atomic64);
 230}
 231
 232/**
 233 * tracing_map_add_var - Add a field describing a tracing_map var
 234 * @map: The tracing_map
 235 *
 236 * Add a var to the map and return the index identifying it in the map
 237 * and associated tracing_map_elts.  This is the index used for
 238 * instance to update a var for a particular tracing_map_elt using
 239 * tracing_map_update_var() or reading it via tracing_map_read_var().
 240 *
 241 * Return: The index identifying the var in the map and associated
 242 * tracing_map_elts, or -EINVAL on error.
 243 */
 244int tracing_map_add_var(struct tracing_map *map)
 245{
 246	int ret = -EINVAL;
 247
 248	if (map->n_vars < TRACING_MAP_VARS_MAX)
 249		ret = map->n_vars++;
 250
 251	return ret;
 252}
 253
 254/**
 255 * tracing_map_add_key_field - Add a field describing a tracing_map key
 256 * @map: The tracing_map
 257 * @offset: The offset within the key
 258 * @cmp_fn: The comparison function that will be used to sort on the key
 259 *
 260 * Let the map know there is a key and that if it's used as a sort key
 261 * to use cmp_fn.
 262 *
 263 * A key can be a subset of a compound key; for that purpose, the
 264 * offset param is used to describe where within the compound key
 265 * the key referenced by this key field resides.
 266 *
 267 * Return: The index identifying the field in the map and associated
 268 * tracing_map_elts, or -EINVAL on error.
 269 */
 270int tracing_map_add_key_field(struct tracing_map *map,
 271			      unsigned int offset,
 272			      tracing_map_cmp_fn_t cmp_fn)
 273
 274{
 275	int idx = tracing_map_add_field(map, cmp_fn);
 276
 277	if (idx < 0)
 278		return idx;
 279
 280	map->fields[idx].offset = offset;
 281
 282	map->key_idx[map->n_keys++] = idx;
 283
 284	return idx;
 285}
 286
 287static void tracing_map_array_clear(struct tracing_map_array *a)
 288{
 289	unsigned int i;
 290
 291	if (!a->pages)
 292		return;
 293
 294	for (i = 0; i < a->n_pages; i++)
 295		memset(a->pages[i], 0, PAGE_SIZE);
 296}
 297
 298static void tracing_map_array_free(struct tracing_map_array *a)
 299{
 300	unsigned int i;
 301
 302	if (!a)
 303		return;
 304
 305	if (!a->pages)
 306		goto free;
 307
 308	for (i = 0; i < a->n_pages; i++) {
 309		if (!a->pages[i])
 310			break;
 311		kmemleak_free(a->pages[i]);
 312		free_page((unsigned long)a->pages[i]);
 313	}
 314
 315	kfree(a->pages);
 316
 317 free:
 318	kfree(a);
 319}
 320
 321static struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
 322						  unsigned int entry_size)
 323{
 324	struct tracing_map_array *a;
 325	unsigned int i;
 326
 327	a = kzalloc(sizeof(*a), GFP_KERNEL);
 328	if (!a)
 329		return NULL;
 330
 331	a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
 332	a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
 333	a->n_pages = n_elts / a->entries_per_page;
 334	if (!a->n_pages)
 335		a->n_pages = 1;
 336	a->entry_shift = fls(a->entries_per_page) - 1;
 337	a->entry_mask = (1 << a->entry_shift) - 1;
 338
 339	a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
 340	if (!a->pages)
 341		goto free;
 342
 343	for (i = 0; i < a->n_pages; i++) {
 344		a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
 345		if (!a->pages[i])
 346			goto free;
 347		kmemleak_alloc(a->pages[i], PAGE_SIZE, 1, GFP_KERNEL);
 348	}
 349 out:
 350	return a;
 351 free:
 352	tracing_map_array_free(a);
 353	a = NULL;
 354
 355	goto out;
 356}
 357
 358static void tracing_map_elt_clear(struct tracing_map_elt *elt)
 359{
 360	unsigned i;
 361
 362	for (i = 0; i < elt->map->n_fields; i++)
 363		if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64)
 364			atomic64_set(&elt->fields[i].sum, 0);
 365
 366	for (i = 0; i < elt->map->n_vars; i++) {
 367		atomic64_set(&elt->vars[i], 0);
 368		elt->var_set[i] = false;
 369	}
 370
 371	if (elt->map->ops && elt->map->ops->elt_clear)
 372		elt->map->ops->elt_clear(elt);
 373}
 374
 375static void tracing_map_elt_init_fields(struct tracing_map_elt *elt)
 376{
 377	unsigned int i;
 378
 379	tracing_map_elt_clear(elt);
 380
 381	for (i = 0; i < elt->map->n_fields; i++) {
 382		elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn;
 383
 384		if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64)
 385			elt->fields[i].offset = elt->map->fields[i].offset;
 386	}
 387}
 388
 389static void tracing_map_elt_free(struct tracing_map_elt *elt)
 390{
 391	if (!elt)
 392		return;
 393
 394	if (elt->map->ops && elt->map->ops->elt_free)
 395		elt->map->ops->elt_free(elt);
 396	kfree(elt->fields);
 397	kfree(elt->vars);
 398	kfree(elt->var_set);
 399	kfree(elt->key);
 400	kfree(elt);
 401}
 402
 403static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map)
 404{
 405	struct tracing_map_elt *elt;
 406	int err = 0;
 407
 408	elt = kzalloc(sizeof(*elt), GFP_KERNEL);
 409	if (!elt)
 410		return ERR_PTR(-ENOMEM);
 411
 412	elt->map = map;
 413
 414	elt->key = kzalloc(map->key_size, GFP_KERNEL);
 415	if (!elt->key) {
 416		err = -ENOMEM;
 417		goto free;
 418	}
 419
 420	elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);
 421	if (!elt->fields) {
 422		err = -ENOMEM;
 423		goto free;
 424	}
 425
 426	elt->vars = kcalloc(map->n_vars, sizeof(*elt->vars), GFP_KERNEL);
 427	if (!elt->vars) {
 428		err = -ENOMEM;
 429		goto free;
 430	}
 431
 432	elt->var_set = kcalloc(map->n_vars, sizeof(*elt->var_set), GFP_KERNEL);
 433	if (!elt->var_set) {
 434		err = -ENOMEM;
 435		goto free;
 436	}
 437
 438	tracing_map_elt_init_fields(elt);
 439
 440	if (map->ops && map->ops->elt_alloc) {
 441		err = map->ops->elt_alloc(elt);
 442		if (err)
 443			goto free;
 444	}
 445	return elt;
 446 free:
 447	tracing_map_elt_free(elt);
 448
 449	return ERR_PTR(err);
 450}
 451
 452static struct tracing_map_elt *get_free_elt(struct tracing_map *map)
 453{
 454	struct tracing_map_elt *elt = NULL;
 455	int idx;
 456
 457	idx = atomic_inc_return(&map->next_elt);
 458	if (idx < map->max_elts) {
 459		elt = *(TRACING_MAP_ELT(map->elts, idx));
 460		if (map->ops && map->ops->elt_init)
 461			map->ops->elt_init(elt);
 462	}
 463
 464	return elt;
 465}
 466
 467static void tracing_map_free_elts(struct tracing_map *map)
 468{
 469	unsigned int i;
 470
 471	if (!map->elts)
 472		return;
 473
 474	for (i = 0; i < map->max_elts; i++) {
 475		tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i)));
 476		*(TRACING_MAP_ELT(map->elts, i)) = NULL;
 477	}
 478
 479	tracing_map_array_free(map->elts);
 480	map->elts = NULL;
 481}
 482
 483static int tracing_map_alloc_elts(struct tracing_map *map)
 484{
 485	unsigned int i;
 486
 487	map->elts = tracing_map_array_alloc(map->max_elts,
 488					    sizeof(struct tracing_map_elt *));
 489	if (!map->elts)
 490		return -ENOMEM;
 491
 492	for (i = 0; i < map->max_elts; i++) {
 493		*(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map);
 494		if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) {
 495			*(TRACING_MAP_ELT(map->elts, i)) = NULL;
 496			tracing_map_free_elts(map);
 497
 498			return -ENOMEM;
 499		}
 500	}
 501
 502	return 0;
 503}
 504
 505static inline bool keys_match(void *key, void *test_key, unsigned key_size)
 506{
 507	bool match = true;
 508
 509	if (memcmp(key, test_key, key_size))
 510		match = false;
 511
 512	return match;
 513}
 514
 515static inline struct tracing_map_elt *
 516__tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only)
 517{
 518	u32 idx, key_hash, test_key;
 519	int dup_try = 0;
 520	struct tracing_map_entry *entry;
 521	struct tracing_map_elt *val;
 522
 523	key_hash = jhash(key, map->key_size, 0);
 524	if (key_hash == 0)
 525		key_hash = 1;
 526	idx = key_hash >> (32 - (map->map_bits + 1));
 527
 528	while (1) {
 529		idx &= (map->map_size - 1);
 530		entry = TRACING_MAP_ENTRY(map->map, idx);
 531		test_key = entry->key;
 532
 533		if (test_key && test_key == key_hash) {
 534			val = READ_ONCE(entry->val);
 535			if (val &&
 536			    keys_match(key, val->key, map->key_size)) {
 537				if (!lookup_only)
 538					atomic64_inc(&map->hits);
 539				return val;
 540			} else if (unlikely(!val)) {
 541				/*
 542				 * The key is present. But, val (pointer to elt
 543				 * struct) is still NULL. which means some other
 544				 * thread is in the process of inserting an
 545				 * element.
 546				 *
 547				 * On top of that, it's key_hash is same as the
 548				 * one being inserted right now. So, it's
 549				 * possible that the element has the same
 550				 * key as well.
 551				 */
 552
 553				dup_try++;
 554				if (dup_try > map->map_size) {
 555					atomic64_inc(&map->drops);
 556					break;
 557				}
 558				continue;
 559			}
 560		}
 561
 562		if (!test_key) {
 563			if (lookup_only)
 564				break;
 565
 566			if (!cmpxchg(&entry->key, 0, key_hash)) {
 567				struct tracing_map_elt *elt;
 568
 569				elt = get_free_elt(map);
 570				if (!elt) {
 571					atomic64_inc(&map->drops);
 572					entry->key = 0;
 573					break;
 574				}
 575
 576				memcpy(elt->key, key, map->key_size);
 577				/*
 578				 * Ensure the initialization is visible and
 579				 * publish the elt.
 580				 */
 581				smp_wmb();
 582				WRITE_ONCE(entry->val, elt);
 583				atomic64_inc(&map->hits);
 584
 585				return entry->val;
 586			} else {
 587				/*
 588				 * cmpxchg() failed. Loop around once
 589				 * more to check what key was inserted.
 590				 */
 591				dup_try++;
 592				continue;
 593			}
 594		}
 595
 596		idx++;
 597	}
 598
 599	return NULL;
 600}
 601
 602/**
 603 * tracing_map_insert - Insert key and/or retrieve val from a tracing_map
 604 * @map: The tracing_map to insert into
 605 * @key: The key to insert
 606 *
 607 * Inserts a key into a tracing_map and creates and returns a new
 608 * tracing_map_elt for it, or if the key has already been inserted by
 609 * a previous call, returns the tracing_map_elt already associated
 610 * with it.  When the map was created, the number of elements to be
 611 * allocated for the map was specified (internally maintained as
 612 * 'max_elts' in struct tracing_map), and that number of
 613 * tracing_map_elts was created by tracing_map_init().  This is the
 614 * pre-allocated pool of tracing_map_elts that tracing_map_insert()
 615 * will allocate from when adding new keys.  Once that pool is
 616 * exhausted, tracing_map_insert() is useless and will return NULL to
 617 * signal that state.  There are two user-visible tracing_map
 618 * variables, 'hits' and 'drops', which are updated by this function.
 619 * Every time an element is either successfully inserted or retrieved,
 620 * the 'hits' value is incremented.  Every time an element insertion
 621 * fails, the 'drops' value is incremented.
 622 *
 623 * This is a lock-free tracing map insertion function implementing a
 624 * modified form of Cliff Click's basic insertion algorithm.  It
 625 * requires the table size be a power of two.  To prevent any
 626 * possibility of an infinite loop we always make the internal table
 627 * size double the size of the requested table size (max_elts * 2).
 628 * Likewise, we never reuse a slot or resize or delete elements - when
 629 * we've reached max_elts entries, we simply return NULL once we've
 630 * run out of entries.  Readers can at any point in time traverse the
 631 * tracing map and safely access the key/val pairs.
 632 *
 633 * Return: the tracing_map_elt pointer val associated with the key.
 634 * If this was a newly inserted key, the val will be a newly allocated
 635 * and associated tracing_map_elt pointer val.  If the key wasn't
 636 * found and the pool of tracing_map_elts has been exhausted, NULL is
 637 * returned and no further insertions will succeed.
 638 */
 639struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)
 640{
 641	return __tracing_map_insert(map, key, false);
 642}
 643
 644/**
 645 * tracing_map_lookup - Retrieve val from a tracing_map
 646 * @map: The tracing_map to perform the lookup on
 647 * @key: The key to look up
 648 *
 649 * Looks up key in tracing_map and if found returns the matching
 650 * tracing_map_elt.  This is a lock-free lookup; see
 651 * tracing_map_insert() for details on tracing_map and how it works.
 652 * Every time an element is retrieved, the 'hits' value is
 653 * incremented.  There is one user-visible tracing_map variable,
 654 * 'hits', which is updated by this function.  Every time an element
 655 * is successfully retrieved, the 'hits' value is incremented.  The
 656 * 'drops' value is never updated by this function.
 657 *
 658 * Return: the tracing_map_elt pointer val associated with the key.
 659 * If the key wasn't found, NULL is returned.
 660 */
 661struct tracing_map_elt *tracing_map_lookup(struct tracing_map *map, void *key)
 662{
 663	return __tracing_map_insert(map, key, true);
 664}
 665
 666/**
 667 * tracing_map_destroy - Destroy a tracing_map
 668 * @map: The tracing_map to destroy
 669 *
 670 * Frees a tracing_map along with its associated array of
 671 * tracing_map_elts.
 672 *
 673 * Callers should make sure there are no readers or writers actively
 674 * reading or inserting into the map before calling this.
 675 */
 676void tracing_map_destroy(struct tracing_map *map)
 677{
 678	if (!map)
 679		return;
 680
 681	tracing_map_free_elts(map);
 682
 683	tracing_map_array_free(map->map);
 684	kfree(map);
 685}
 686
 687/**
 688 * tracing_map_clear - Clear a tracing_map
 689 * @map: The tracing_map to clear
 690 *
 691 * Resets the tracing map to a cleared or initial state.  The
 692 * tracing_map_elts are all cleared, and the array of struct
 693 * tracing_map_entry is reset to an initialized state.
 694 *
 695 * Callers should make sure there are no writers actively inserting
 696 * into the map before calling this.
 697 */
 698void tracing_map_clear(struct tracing_map *map)
 699{
 700	unsigned int i;
 701
 702	atomic_set(&map->next_elt, -1);
 703	atomic64_set(&map->hits, 0);
 704	atomic64_set(&map->drops, 0);
 705
 706	tracing_map_array_clear(map->map);
 707
 708	for (i = 0; i < map->max_elts; i++)
 709		tracing_map_elt_clear(*(TRACING_MAP_ELT(map->elts, i)));
 710}
 711
 712static void set_sort_key(struct tracing_map *map,
 713			 struct tracing_map_sort_key *sort_key)
 714{
 715	map->sort_key = *sort_key;
 716}
 717
 718/**
 719 * tracing_map_create - Create a lock-free map and element pool
 720 * @map_bits: The size of the map (2 ** map_bits)
 721 * @key_size: The size of the key for the map in bytes
 722 * @ops: Optional client-defined tracing_map_ops instance
 723 * @private_data: Client data associated with the map
 724 *
 725 * Creates and sets up a map to contain 2 ** map_bits number of
 726 * elements (internally maintained as 'max_elts' in struct
 727 * tracing_map).  Before using, map fields should be added to the map
 728 * with tracing_map_add_sum_field() and tracing_map_add_key_field().
 729 * tracing_map_init() should then be called to allocate the array of
 730 * tracing_map_elts, in order to avoid allocating anything in the map
 731 * insertion path.  The user-specified map size reflects the maximum
 732 * number of elements that can be contained in the table requested by
 733 * the user - internally we double that in order to keep the table
 734 * sparse and keep collisions manageable.
 735 *
 736 * A tracing_map is a special-purpose map designed to aggregate or
 737 * 'sum' one or more values associated with a specific object of type
 738 * tracing_map_elt, which is attached by the map to a given key.
 739 *
 740 * tracing_map_create() sets up the map itself, and provides
 741 * operations for inserting tracing_map_elts, but doesn't allocate the
 742 * tracing_map_elts themselves, or provide a means for describing the
 743 * keys or sums associated with the tracing_map_elts.  All
 744 * tracing_map_elts for a given map have the same set of sums and
 745 * keys, which are defined by the client using the functions
 746 * tracing_map_add_key_field() and tracing_map_add_sum_field().  Once
 747 * the fields are defined, the pool of elements allocated for the map
 748 * can be created, which occurs when the client code calls
 749 * tracing_map_init().
 750 *
 751 * When tracing_map_init() returns, tracing_map_elt elements can be
 752 * inserted into the map using tracing_map_insert().  When called,
 753 * tracing_map_insert() grabs a free tracing_map_elt from the pool, or
 754 * finds an existing match in the map and in either case returns it.
 755 * The client can then use tracing_map_update_sum() and
 756 * tracing_map_read_sum() to update or read a given sum field for the
 757 * tracing_map_elt.
 758 *
 759 * The client can at any point retrieve and traverse the current set
 760 * of inserted tracing_map_elts in a tracing_map, via
 761 * tracing_map_sort_entries().  Sorting can be done on any field,
 762 * including keys.
 763 *
 764 * See tracing_map.h for a description of tracing_map_ops.
 765 *
 766 * Return: the tracing_map pointer if successful, ERR_PTR if not.
 767 */
 768struct tracing_map *tracing_map_create(unsigned int map_bits,
 769				       unsigned int key_size,
 770				       const struct tracing_map_ops *ops,
 771				       void *private_data)
 772{
 773	struct tracing_map *map;
 774	unsigned int i;
 775
 776	if (map_bits < TRACING_MAP_BITS_MIN ||
 777	    map_bits > TRACING_MAP_BITS_MAX)
 778		return ERR_PTR(-EINVAL);
 779
 780	map = kzalloc(sizeof(*map), GFP_KERNEL);
 781	if (!map)
 782		return ERR_PTR(-ENOMEM);
 783
 784	map->map_bits = map_bits;
 785	map->max_elts = (1 << map_bits);
 786	atomic_set(&map->next_elt, -1);
 787
 788	map->map_size = (1 << (map_bits + 1));
 789	map->ops = ops;
 790
 791	map->private_data = private_data;
 792
 793	map->map = tracing_map_array_alloc(map->map_size,
 794					   sizeof(struct tracing_map_entry));
 795	if (!map->map)
 796		goto free;
 797
 798	map->key_size = key_size;
 799	for (i = 0; i < TRACING_MAP_KEYS_MAX; i++)
 800		map->key_idx[i] = -1;
 801 out:
 802	return map;
 803 free:
 804	tracing_map_destroy(map);
 805	map = ERR_PTR(-ENOMEM);
 806
 807	goto out;
 808}
 809
 810/**
 811 * tracing_map_init - Allocate and clear a map's tracing_map_elts
 812 * @map: The tracing_map to initialize
 813 *
 814 * Allocates a clears a pool of tracing_map_elts equal to the
 815 * user-specified size of 2 ** map_bits (internally maintained as
 816 * 'max_elts' in struct tracing_map).  Before using, the map fields
 817 * should be added to the map with tracing_map_add_sum_field() and
 818 * tracing_map_add_key_field().  tracing_map_init() should then be
 819 * called to allocate the array of tracing_map_elts, in order to avoid
 820 * allocating anything in the map insertion path.  The user-specified
 821 * map size reflects the max number of elements requested by the user
 822 * - internally we double that in order to keep the table sparse and
 823 * keep collisions manageable.
 824 *
 825 * See tracing_map.h for a description of tracing_map_ops.
 826 *
 827 * Return: the tracing_map pointer if successful, ERR_PTR if not.
 828 */
 829int tracing_map_init(struct tracing_map *map)
 830{
 831	int err;
 832
 833	if (map->n_fields < 2)
 834		return -EINVAL; /* need at least 1 key and 1 val */
 835
 836	err = tracing_map_alloc_elts(map);
 837	if (err)
 838		return err;
 839
 840	tracing_map_clear(map);
 841
 842	return err;
 843}
 844
 845static int cmp_entries_dup(const void *A, const void *B)
 846{
 847	const struct tracing_map_sort_entry *a, *b;
 848	int ret = 0;
 849
 850	a = *(const struct tracing_map_sort_entry **)A;
 851	b = *(const struct tracing_map_sort_entry **)B;
 852
 853	if (memcmp(a->key, b->key, a->elt->map->key_size))
 854		ret = 1;
 855
 856	return ret;
 857}
 858
 859static int cmp_entries_sum(const void *A, const void *B)
 860{
 861	const struct tracing_map_elt *elt_a, *elt_b;
 862	const struct tracing_map_sort_entry *a, *b;
 863	struct tracing_map_sort_key *sort_key;
 864	struct tracing_map_field *field;
 865	tracing_map_cmp_fn_t cmp_fn;
 866	void *val_a, *val_b;
 867	int ret = 0;
 868
 869	a = *(const struct tracing_map_sort_entry **)A;
 870	b = *(const struct tracing_map_sort_entry **)B;
 871
 872	elt_a = a->elt;
 873	elt_b = b->elt;
 874
 875	sort_key = &elt_a->map->sort_key;
 876
 877	field = &elt_a->fields[sort_key->field_idx];
 878	cmp_fn = field->cmp_fn;
 879
 880	val_a = &elt_a->fields[sort_key->field_idx].sum;
 881	val_b = &elt_b->fields[sort_key->field_idx].sum;
 882
 883	ret = cmp_fn(val_a, val_b);
 884	if (sort_key->descending)
 885		ret = -ret;
 886
 887	return ret;
 888}
 889
 890static int cmp_entries_key(const void *A, const void *B)
 891{
 892	const struct tracing_map_elt *elt_a, *elt_b;
 893	const struct tracing_map_sort_entry *a, *b;
 894	struct tracing_map_sort_key *sort_key;
 895	struct tracing_map_field *field;
 896	tracing_map_cmp_fn_t cmp_fn;
 897	void *val_a, *val_b;
 898	int ret = 0;
 899
 900	a = *(const struct tracing_map_sort_entry **)A;
 901	b = *(const struct tracing_map_sort_entry **)B;
 902
 903	elt_a = a->elt;
 904	elt_b = b->elt;
 905
 906	sort_key = &elt_a->map->sort_key;
 907
 908	field = &elt_a->fields[sort_key->field_idx];
 909
 910	cmp_fn = field->cmp_fn;
 911
 912	val_a = elt_a->key + field->offset;
 913	val_b = elt_b->key + field->offset;
 914
 915	ret = cmp_fn(val_a, val_b);
 916	if (sort_key->descending)
 917		ret = -ret;
 918
 919	return ret;
 920}
 921
 922static void destroy_sort_entry(struct tracing_map_sort_entry *entry)
 923{
 924	if (!entry)
 925		return;
 926
 927	if (entry->elt_copied)
 928		tracing_map_elt_free(entry->elt);
 929
 930	kfree(entry);
 931}
 932
 933/**
 934 * tracing_map_destroy_sort_entries - Destroy an array of sort entries
 935 * @entries: The entries to destroy
 936 * @n_entries: The number of entries in the array
 937 *
 938 * Destroy the elements returned by a tracing_map_sort_entries() call.
 939 */
 940void tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries,
 941				      unsigned int n_entries)
 942{
 943	unsigned int i;
 944
 945	for (i = 0; i < n_entries; i++)
 946		destroy_sort_entry(entries[i]);
 947
 948	vfree(entries);
 949}
 950
 951static struct tracing_map_sort_entry *
 952create_sort_entry(void *key, struct tracing_map_elt *elt)
 953{
 954	struct tracing_map_sort_entry *sort_entry;
 955
 956	sort_entry = kzalloc(sizeof(*sort_entry), GFP_KERNEL);
 957	if (!sort_entry)
 958		return NULL;
 959
 960	sort_entry->key = key;
 961	sort_entry->elt = elt;
 962
 963	return sort_entry;
 964}
 965
 966static void detect_dups(struct tracing_map_sort_entry **sort_entries,
 967		      int n_entries, unsigned int key_size)
 968{
 969	unsigned int total_dups = 0;
 970	int i;
 971	void *key;
 972
 973	if (n_entries < 2)
 974		return;
 975
 976	sort(sort_entries, n_entries, sizeof(struct tracing_map_sort_entry *),
 977	     (int (*)(const void *, const void *))cmp_entries_dup, NULL);
 978
 979	key = sort_entries[0]->key;
 980	for (i = 1; i < n_entries; i++) {
 981		if (!memcmp(sort_entries[i]->key, key, key_size)) {
 982			total_dups++;
 983			continue;
 984		}
 985		key = sort_entries[i]->key;
 986	}
 987
 988	WARN_ONCE(total_dups > 0,
 989		  "Duplicates detected: %d\n", total_dups);
 990}
 991
 992static bool is_key(struct tracing_map *map, unsigned int field_idx)
 993{
 994	unsigned int i;
 995
 996	for (i = 0; i < map->n_keys; i++)
 997		if (map->key_idx[i] == field_idx)
 998			return true;
 999	return false;
1000}
1001
1002static void sort_secondary(struct tracing_map *map,
1003			   const struct tracing_map_sort_entry **entries,
1004			   unsigned int n_entries,
1005			   struct tracing_map_sort_key *primary_key,
1006			   struct tracing_map_sort_key *secondary_key)
1007{
1008	int (*primary_fn)(const void *, const void *);
1009	int (*secondary_fn)(const void *, const void *);
1010	unsigned i, start = 0, n_sub = 1;
1011
1012	if (is_key(map, primary_key->field_idx))
1013		primary_fn = cmp_entries_key;
1014	else
1015		primary_fn = cmp_entries_sum;
1016
1017	if (is_key(map, secondary_key->field_idx))
1018		secondary_fn = cmp_entries_key;
1019	else
1020		secondary_fn = cmp_entries_sum;
1021
1022	for (i = 0; i < n_entries - 1; i++) {
1023		const struct tracing_map_sort_entry **a = &entries[i];
1024		const struct tracing_map_sort_entry **b = &entries[i + 1];
1025
1026		if (primary_fn(a, b) == 0) {
1027			n_sub++;
1028			if (i < n_entries - 2)
1029				continue;
1030		}
1031
1032		if (n_sub < 2) {
1033			start = i + 1;
1034			n_sub = 1;
1035			continue;
1036		}
1037
1038		set_sort_key(map, secondary_key);
1039		sort(&entries[start], n_sub,
1040		     sizeof(struct tracing_map_sort_entry *),
1041		     (int (*)(const void *, const void *))secondary_fn, NULL);
1042		set_sort_key(map, primary_key);
1043
1044		start = i + 1;
1045		n_sub = 1;
1046	}
1047}
1048
1049/**
1050 * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
1051 * @map: The tracing_map
1052 * @sort_keys: The sort key to use for sorting
1053 * @n_sort_keys: hitcount, always have at least one
1054 * @sort_entries: outval: pointer to allocated and sorted array of entries
1055 *
1056 * tracing_map_sort_entries() sorts the current set of entries in the
1057 * map and returns the list of tracing_map_sort_entries containing
1058 * them to the client in the sort_entries param.  The client can
1059 * access the struct tracing_map_elt element of interest directly as
1060 * the 'elt' field of a returned struct tracing_map_sort_entry object.
1061 *
1062 * The sort_key has only two fields: idx and descending.  'idx' refers
1063 * to the index of the field added via tracing_map_add_sum_field() or
1064 * tracing_map_add_key_field() when the tracing_map was initialized.
1065 * 'descending' is a flag that if set reverses the sort order, which
1066 * by default is ascending.
1067 *
1068 * The client should not hold on to the returned array but should use
1069 * it and call tracing_map_destroy_sort_entries() when done.
1070 *
1071 * Return: the number of sort_entries in the struct tracing_map_sort_entry
1072 * array, negative on error
1073 */
1074int tracing_map_sort_entries(struct tracing_map *map,
1075			     struct tracing_map_sort_key *sort_keys,
1076			     unsigned int n_sort_keys,
1077			     struct tracing_map_sort_entry ***sort_entries)
1078{
1079	int (*cmp_entries_fn)(const void *, const void *);
1080	struct tracing_map_sort_entry *sort_entry, **entries;
1081	int i, n_entries, ret;
1082
1083	entries = vmalloc(array_size(sizeof(sort_entry), map->max_elts));
1084	if (!entries)
1085		return -ENOMEM;
1086
1087	for (i = 0, n_entries = 0; i < map->map_size; i++) {
1088		struct tracing_map_entry *entry;
1089
1090		entry = TRACING_MAP_ENTRY(map->map, i);
1091
1092		if (!entry->key || !entry->val)
1093			continue;
1094
1095		entries[n_entries] = create_sort_entry(entry->val->key,
1096						       entry->val);
1097		if (!entries[n_entries++]) {
1098			ret = -ENOMEM;
1099			goto free;
1100		}
1101	}
1102
1103	if (n_entries == 0) {
1104		ret = 0;
1105		goto free;
1106	}
1107
1108	if (n_entries == 1) {
1109		*sort_entries = entries;
1110		return 1;
1111	}
1112
1113	detect_dups(entries, n_entries, map->key_size);
1114
1115	if (is_key(map, sort_keys[0].field_idx))
1116		cmp_entries_fn = cmp_entries_key;
1117	else
1118		cmp_entries_fn = cmp_entries_sum;
1119
1120	set_sort_key(map, &sort_keys[0]);
1121
1122	sort(entries, n_entries, sizeof(struct tracing_map_sort_entry *),
1123	     (int (*)(const void *, const void *))cmp_entries_fn, NULL);
1124
1125	if (n_sort_keys > 1)
1126		sort_secondary(map,
1127			       (const struct tracing_map_sort_entry **)entries,
1128			       n_entries,
1129			       &sort_keys[0],
1130			       &sort_keys[1]);
1131
1132	*sort_entries = entries;
1133
1134	return n_entries;
1135 free:
1136	tracing_map_destroy_sort_entries(entries, n_entries);
1137
1138	return ret;
1139}