1 // SPDX-License-Identifier: GPL-2.0
3  * tracing_map - lock-free map for tracing
7  * tracing_map implementation inspired by lock-free map algorithms
10  * http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable
30  * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
37  * tracing_map_add_sum_field() when the tracing map was set up.
41 	atomic64_add(n, &elt->fields[i].sum);  in tracing_map_update_sum()
45  * tracing_map_read_sum - Return the value of a tracing_map_elt's sum field
52  * up.
58 	return (u64)atomic64_read(&elt->fields[i].sum);  in tracing_map_read_sum()
62  * tracing_map_set_var - Assign a tracing_map_elt's variable field
69  * tracing_map_add_var() when the tracing map was set up.
73 	atomic64_set(&elt->vars[i], n);  in tracing_map_set_var()
74 	elt->var_set[i] = true;  in tracing_map_set_var()
78  * tracing_map_var_set - Return whether or not a variable has been set
84  * when the tracing map was set up.
88 	return elt->var_set[i];  in tracing_map_var_set()
92  * tracing_map_read_var - Return the value of a tracing_map_elt's variable field
99  * up.
105 	return (u64)atomic64_read(&elt->vars[i]);  in tracing_map_read_var()
109  * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field
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
124 	elt->var_set[i] = false;  in tracing_map_read_var_once()
125 	return (u64)atomic64_read(&elt->vars[i]);  in tracing_map_read_var_once()
146 	return (a > b) ? 1 : ((a < b) ? -1 : 0);  in tracing_map_cmp_atomic64()
155 	return (a > b) ? 1 : ((a < b) ? -1 : 0);			\
205 	int ret = -EINVAL;  in tracing_map_add_field()
207 	if (map->n_fields < TRACING_MAP_FIELDS_MAX) {  in tracing_map_add_field()
208 		ret = map->n_fields;  in tracing_map_add_field()
209 		map->fields[map->n_fields++].cmp_fn = cmp_fn;  in tracing_map_add_field()
216  * tracing_map_add_sum_field - Add a field describing a tracing_map sum
219  * Add a sum field to the key and return the index identifying it in
225  * tracing_map_elts, or -EINVAL on error.
233  * tracing_map_add_var - Add a field describing a tracing_map var
242  * tracing_map_elts, or -EINVAL on error.
246 	int ret = -EINVAL;  in tracing_map_add_var()
248 	if (map->n_vars < TRACING_MAP_VARS_MAX)  in tracing_map_add_var()
249 		ret = map->n_vars++;  in tracing_map_add_var()
255  * tracing_map_add_key_field - Add a field describing a tracing_map key
257  * @offset: The offset within the key
258  * @cmp_fn: The comparison function that will be used to sort on the key
260  * Let the map know there is a key and that if it's used as a sort key
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.
268  * tracing_map_elts, or -EINVAL on error.
280 	map->fields[idx].offset = offset;  in tracing_map_add_key_field()
282 	map->key_idx[map->n_keys++] = idx;  in tracing_map_add_key_field()
291 	if (!a->pages)  in tracing_map_array_clear()
294 	for (i = 0; i < a->n_pages; i++)  in tracing_map_array_clear()
295 		memset(a->pages[i], 0, PAGE_SIZE);  in tracing_map_array_clear()
305 	if (!a->pages)  in tracing_map_array_free()
308 	for (i = 0; i < a->n_pages; i++) {  in tracing_map_array_free()
309 		if (!a->pages[i])  in tracing_map_array_free()
311 		kmemleak_free(a->pages[i]);  in tracing_map_array_free()
312 		free_page((unsigned long)a->pages[i]);  in tracing_map_array_free()
315 	kfree(a->pages);  in tracing_map_array_free()
331 	a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);  in tracing_map_array_alloc()
332 	a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);  in tracing_map_array_alloc()
333 	a->n_pages = n_elts / a->entries_per_page;  in tracing_map_array_alloc()
334 	if (!a->n_pages)  in tracing_map_array_alloc()
335 		a->n_pages = 1;  in tracing_map_array_alloc()
336 	a->entry_shift = fls(a->entries_per_page) - 1;  in tracing_map_array_alloc()
337 	a->entry_mask = (1 << a->entry_shift) - 1;  in tracing_map_array_alloc()
339 	a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);  in tracing_map_array_alloc()
340 	if (!a->pages)  in tracing_map_array_alloc()
343 	for (i = 0; i < a->n_pages; i++) {  in tracing_map_array_alloc()
344 		a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);  in tracing_map_array_alloc()
345 		if (!a->pages[i])  in tracing_map_array_alloc()
347 		kmemleak_alloc(a->pages[i], PAGE_SIZE, 1, GFP_KERNEL);  in tracing_map_array_alloc()
362 	for (i = 0; i < elt->map->n_fields; i++)  in tracing_map_elt_clear()
363 		if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64)  in tracing_map_elt_clear()
364 			atomic64_set(&elt->fields[i].sum, 0);  in tracing_map_elt_clear()
366 	for (i = 0; i < elt->map->n_vars; i++) {  in tracing_map_elt_clear()
367 		atomic64_set(&elt->vars[i], 0);  in tracing_map_elt_clear()
368 		elt->var_set[i] = false;  in tracing_map_elt_clear()
371 	if (elt->map->ops && elt->map->ops->elt_clear)  in tracing_map_elt_clear()
372 		elt->map->ops->elt_clear(elt);  in tracing_map_elt_clear()
381 	for (i = 0; i < elt->map->n_fields; i++) {  in tracing_map_elt_init_fields()
382 		elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn;  in tracing_map_elt_init_fields()
384 		if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64)  in tracing_map_elt_init_fields()
385 			elt->fields[i].offset = elt->map->fields[i].offset;  in tracing_map_elt_init_fields()
394 	if (elt->map->ops && elt->map->ops->elt_free)  in tracing_map_elt_free()
395 		elt->map->ops->elt_free(elt);  in tracing_map_elt_free()
396 	kfree(elt->fields);  in tracing_map_elt_free()
397 	kfree(elt->vars);  in tracing_map_elt_free()
398 	kfree(elt->var_set);  in tracing_map_elt_free()
399 	kfree(elt->key);  in tracing_map_elt_free()
410 		return ERR_PTR(-ENOMEM);  in tracing_map_elt_alloc()
412 	elt->map = map;  in tracing_map_elt_alloc()
414 	elt->key = kzalloc(map->key_size, GFP_KERNEL);  in tracing_map_elt_alloc()
415 	if (!elt->key) {  in tracing_map_elt_alloc()
416 		err = -ENOMEM;  in tracing_map_elt_alloc()
420 	elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);  in tracing_map_elt_alloc()
421 	if (!elt->fields) {  in tracing_map_elt_alloc()
422 		err = -ENOMEM;  in tracing_map_elt_alloc()
426 	elt->vars = kcalloc(map->n_vars, sizeof(*elt->vars), GFP_KERNEL);  in tracing_map_elt_alloc()
427 	if (!elt->vars) {  in tracing_map_elt_alloc()
428 		err = -ENOMEM;  in tracing_map_elt_alloc()
432 	elt->var_set = kcalloc(map->n_vars, sizeof(*elt->var_set), GFP_KERNEL);  in tracing_map_elt_alloc()
433 	if (!elt->var_set) {  in tracing_map_elt_alloc()
434 		err = -ENOMEM;  in tracing_map_elt_alloc()
440 	if (map->ops && map->ops->elt_alloc) {  in tracing_map_elt_alloc()
441 		err = map->ops->elt_alloc(elt);  in tracing_map_elt_alloc()
457 	idx = atomic_inc_return(&map->next_elt);  in get_free_elt()
458 	if (idx < map->max_elts) {  in get_free_elt()
459 		elt = *(TRACING_MAP_ELT(map->elts, idx));  in get_free_elt()
460 		if (map->ops && map->ops->elt_init)  in get_free_elt()
461 			map->ops->elt_init(elt);  in get_free_elt()
471 	if (!map->elts)  in tracing_map_free_elts()
474 	for (i = 0; i < map->max_elts; i++) {  in tracing_map_free_elts()
475 		tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i)));  in tracing_map_free_elts()
476 		*(TRACING_MAP_ELT(map->elts, i)) = NULL;  in tracing_map_free_elts()
479 	tracing_map_array_free(map->elts);  in tracing_map_free_elts()
480 	map->elts = NULL;  in tracing_map_free_elts()
487 	map->elts = tracing_map_array_alloc(map->max_elts,  in tracing_map_alloc_elts()
489 	if (!map->elts)  in tracing_map_alloc_elts()
490 		return -ENOMEM;  in tracing_map_alloc_elts()
492 	for (i = 0; i < map->max_elts; i++) {  in tracing_map_alloc_elts()
493 		*(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map);  in tracing_map_alloc_elts()
494 		if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) {  in tracing_map_alloc_elts()
495 			*(TRACING_MAP_ELT(map->elts, i)) = NULL;  in tracing_map_alloc_elts()
498 			return -ENOMEM;  in tracing_map_alloc_elts()
505 static inline bool keys_match(void *key, void *test_key, unsigned key_size)  in keys_match()  argument
509 	if (memcmp(key, test_key, key_size))  in keys_match()
516 __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only)  in __tracing_map_insert()  argument
523 	key_hash = jhash(key, map->key_size, 0);  in __tracing_map_insert()
526 	idx = key_hash >> (32 - (map->map_bits + 1));  in __tracing_map_insert()
529 		idx &= (map->map_size - 1);  in __tracing_map_insert()
530 		entry = TRACING_MAP_ENTRY(map->map, idx);  in __tracing_map_insert()
531 		test_key = entry->key;  in __tracing_map_insert()
534 			val = READ_ONCE(entry->val);  in __tracing_map_insert()
536 			    keys_match(key, val->key, map->key_size)) {  in __tracing_map_insert()
538 					atomic64_inc(&map->hits);  in __tracing_map_insert()
542 				 * The key is present. But, val (pointer to elt  in __tracing_map_insert()
550 				 * key as well.  in __tracing_map_insert()
554 				if (dup_try > map->map_size) {  in __tracing_map_insert()
555 					atomic64_inc(&map->drops);  in __tracing_map_insert()
566 			if (!cmpxchg(&entry->key, 0, key_hash)) {  in __tracing_map_insert()
571 					atomic64_inc(&map->drops);  in __tracing_map_insert()
572 					entry->key = 0;  in __tracing_map_insert()
576 				memcpy(elt->key, key, map->key_size);  in __tracing_map_insert()
582 				WRITE_ONCE(entry->val, elt);  in __tracing_map_insert()
583 				atomic64_inc(&map->hits);  in __tracing_map_insert()
585 				return entry->val;  in __tracing_map_insert()
589 				 * more to check what key was inserted.  in __tracing_map_insert()
603  * tracing_map_insert - Insert key and/or retrieve val from a tracing_map
605  * @key: The key to insert
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
614  * pre-allocated pool of tracing_map_elts that tracing_map_insert()
617  * signal that state.  There are two user-visible tracing_map
623  * This is a lock-free tracing map insertion function implementing a
628  * Likewise, we never reuse a slot or resize or delete elements - when
631  * tracing map and safely access the key/val pairs.
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
639 struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)  in tracing_map_insert()  argument
641 	return __tracing_map_insert(map, key, false);  in tracing_map_insert()
645  * tracing_map_lookup - Retrieve val from a tracing_map
647  * @key: The key to look up
649  * Looks up key in tracing_map and if found returns the matching
650  * tracing_map_elt.  This is a lock-free lookup; see
653  * incremented.  There is one user-visible tracing_map variable,
658  * Return: the tracing_map_elt pointer val associated with the key.
659  * If the key wasn't found, NULL is returned.
661 struct tracing_map_elt *tracing_map_lookup(struct tracing_map *map, void *key)  in tracing_map_lookup()  argument
663 	return __tracing_map_insert(map, key, true);  in tracing_map_lookup()
667  * tracing_map_destroy - Destroy a tracing_map
683 	tracing_map_array_free(map->map);  in tracing_map_destroy()
688  * tracing_map_clear - Clear a tracing_map
702 	atomic_set(&map->next_elt, -1);  in tracing_map_clear()
703 	atomic64_set(&map->hits, 0);  in tracing_map_clear()
704 	atomic64_set(&map->drops, 0);  in tracing_map_clear()
706 	tracing_map_array_clear(map->map);  in tracing_map_clear()
708 	for (i = 0; i < map->max_elts; i++)  in tracing_map_clear()
709 		tracing_map_elt_clear(*(TRACING_MAP_ELT(map->elts, i)));  in tracing_map_clear()
715 	map->sort_key = *sort_key;  in set_sort_key()
719  * tracing_map_create - Create a lock-free map and element pool
721  * @key_size: The size of the key for the map in bytes
722  * @ops: Optional client-defined tracing_map_ops instance
725  * Creates and sets up a map to contain 2 ** map_bits number of
731  * insertion path.  The user-specified map size reflects the maximum
733  * the user - internally we double that in order to keep the table
736  * A tracing_map is a special-purpose map designed to aggregate or
738  * tracing_map_elt, which is attached by the map to a given key.
740  * tracing_map_create() sets up the map itself, and provides
778 		return ERR_PTR(-EINVAL);  in tracing_map_create()
782 		return ERR_PTR(-ENOMEM);  in tracing_map_create()
784 	map->map_bits = map_bits;  in tracing_map_create()
785 	map->max_elts = (1 << map_bits);  in tracing_map_create()
786 	atomic_set(&map->next_elt, -1);  in tracing_map_create()
788 	map->map_size = (1 << (map_bits + 1));  in tracing_map_create()
789 	map->ops = ops;  in tracing_map_create()
791 	map->private_data = private_data;  in tracing_map_create()
793 	map->map = tracing_map_array_alloc(map->map_size,  in tracing_map_create()
795 	if (!map->map)  in tracing_map_create()
798 	map->key_size = key_size;  in tracing_map_create()
800 		map->key_idx[i] = -1;  in tracing_map_create()
805 	map = ERR_PTR(-ENOMEM);  in tracing_map_create()
811  * tracing_map_init - Allocate and clear a map's tracing_map_elts
815  * user-specified size of 2 ** map_bits (internally maintained as
820  * allocating anything in the map insertion path.  The user-specified
822  * - internally we double that in order to keep the table sparse and
833 	if (map->n_fields < 2)  in tracing_map_init()
834 		return -EINVAL; /* need at least 1 key and 1 val */  in tracing_map_init()
853 	if (memcmp(a->key, b->key, a->elt->map->key_size))  in cmp_entries_dup()
872 	elt_a = a->elt;  in cmp_entries_sum()
873 	elt_b = b->elt;  in cmp_entries_sum()
875 	sort_key = &elt_a->map->sort_key;  in cmp_entries_sum()
877 	field = &elt_a->fields[sort_key->field_idx];  in cmp_entries_sum()
878 	cmp_fn = field->cmp_fn;  in cmp_entries_sum()
880 	val_a = &elt_a->fields[sort_key->field_idx].sum;  in cmp_entries_sum()
881 	val_b = &elt_b->fields[sort_key->field_idx].sum;  in cmp_entries_sum()
884 	if (sort_key->descending)  in cmp_entries_sum()
885 		ret = -ret;  in cmp_entries_sum()
903 	elt_a = a->elt;  in cmp_entries_key()
904 	elt_b = b->elt;  in cmp_entries_key()
906 	sort_key = &elt_a->map->sort_key;  in cmp_entries_key()
908 	field = &elt_a->fields[sort_key->field_idx];  in cmp_entries_key()
910 	cmp_fn = field->cmp_fn;  in cmp_entries_key()
912 	val_a = elt_a->key + field->offset;  in cmp_entries_key()
913 	val_b = elt_b->key + field->offset;  in cmp_entries_key()
916 	if (sort_key->descending)  in cmp_entries_key()
917 		ret = -ret;  in cmp_entries_key()
927 	if (entry->elt_copied)  in destroy_sort_entry()
928 		tracing_map_elt_free(entry->elt);  in destroy_sort_entry()
934  * tracing_map_destroy_sort_entries - Destroy an array of sort entries
952 create_sort_entry(void *key, struct tracing_map_elt *elt)  in create_sort_entry()  argument
960 	sort_entry->key = key;  in create_sort_entry()
961 	sort_entry->elt = elt;  in create_sort_entry()
971 	void *key;  in detect_dups()  local
979 	key = sort_entries[0]->key;  in detect_dups()
981 		if (!memcmp(sort_entries[i]->key, key, key_size)) {  in detect_dups()
985 		key = sort_entries[i]->key;  in detect_dups()
996 	for (i = 0; i < map->n_keys; i++)  in is_key()
997 		if (map->key_idx[i] == field_idx)  in is_key()
1012 	if (is_key(map, primary_key->field_idx))  in sort_secondary()
1017 	if (is_key(map, secondary_key->field_idx))  in sort_secondary()
1022 	for (i = 0; i < n_entries - 1; i++) {  in sort_secondary()
1028 			if (i < n_entries - 2)  in sort_secondary()
1050  * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
1052  * @sort_keys: The sort key to use for sorting
1083 	entries = vmalloc(array_size(sizeof(sort_entry), map->max_elts));  in tracing_map_sort_entries()
1085 		return -ENOMEM;  in tracing_map_sort_entries()
1087 	for (i = 0, n_entries = 0; i < map->map_size; i++) {  in tracing_map_sort_entries()
1090 		entry = TRACING_MAP_ENTRY(map->map, i);  in tracing_map_sort_entries()
1092 		if (!entry->key || !entry->val)  in tracing_map_sort_entries()
1095 		entries[n_entries] = create_sort_entry(entry->val->key,  in tracing_map_sort_entries()
1096 						       entry->val);  in tracing_map_sort_entries()
1098 			ret = -ENOMEM;  in tracing_map_sort_entries()
1113 	detect_dups(entries, n_entries, map->key_size);  in tracing_map_sort_entries()