202 static int tracing_map_add_field(struct tracing_map *map,  in tracing_map_add_field()  argument
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()
227 int tracing_map_add_sum_field(struct tracing_map *map)  in tracing_map_add_sum_field()  argument
229 	return tracing_map_add_field(map, tracing_map_cmp_atomic64);  in tracing_map_add_sum_field()
244 int tracing_map_add_var(struct tracing_map *map)  in tracing_map_add_var()  argument
248 	if (map->n_vars < TRACING_MAP_VARS_MAX)  in tracing_map_add_var()
249 		ret = map->n_vars++;  in tracing_map_add_var()
270 int tracing_map_add_key_field(struct tracing_map *map,  in tracing_map_add_key_field()  argument
275 	int idx = tracing_map_add_field(map, cmp_fn);  in tracing_map_add_key_field()
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()
362 	for (i = 0; i < elt->map->n_fields; i++)  in tracing_map_elt_clear()
366 	for (i = 0; i < elt->map->n_vars; i++) {  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()
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()
403 static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map)  in tracing_map_elt_alloc()  argument
412 	elt->map = map;  in tracing_map_elt_alloc()
414 	elt->key = kzalloc(map->key_size, GFP_KERNEL);  in tracing_map_elt_alloc()
420 	elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);  in tracing_map_elt_alloc()
426 	elt->vars = kcalloc(map->n_vars, sizeof(*elt->vars), GFP_KERNEL);  in tracing_map_elt_alloc()
432 	elt->var_set = kcalloc(map->n_vars, sizeof(*elt->var_set), GFP_KERNEL);  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()
452 static struct tracing_map_elt *get_free_elt(struct tracing_map *map)  in get_free_elt()  argument
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()
467 static void tracing_map_free_elts(struct tracing_map *map)  in tracing_map_free_elts()  argument
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()
483 static int tracing_map_alloc_elts(struct tracing_map *map)  in tracing_map_alloc_elts()  argument
487 	map->elts = tracing_map_array_alloc(map->max_elts,  in tracing_map_alloc_elts()
489 	if (!map->elts)  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()
496 			tracing_map_free_elts(map);  in tracing_map_alloc_elts()
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()
536 			    keys_match(key, val->key, map->key_size)) {  in __tracing_map_insert()
538 					atomic64_inc(&map->hits);  in __tracing_map_insert()
554 				if (dup_try > map->map_size) {  in __tracing_map_insert()
555 					atomic64_inc(&map->drops);  in __tracing_map_insert()
569 				elt = get_free_elt(map);  in __tracing_map_insert()
571 					atomic64_inc(&map->drops);  in __tracing_map_insert()
576 				memcpy(elt->key, key, map->key_size);  in __tracing_map_insert()
583 				atomic64_inc(&map->hits);  in __tracing_map_insert()
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()
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()
676 void tracing_map_destroy(struct tracing_map *map)  in tracing_map_destroy()  argument
678 	if (!map)  in tracing_map_destroy()
681 	tracing_map_free_elts(map);  in tracing_map_destroy()
683 	tracing_map_array_free(map->map);  in tracing_map_destroy()
684 	kfree(map);  in tracing_map_destroy()
698 void tracing_map_clear(struct tracing_map *map)  in tracing_map_clear()  argument
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()
712 static void set_sort_key(struct tracing_map *map,  in set_sort_key()  argument
715 	map->sort_key = *sort_key;  in set_sort_key()
773 	struct tracing_map *map;  in tracing_map_create()  local
780 	map = kzalloc(sizeof(*map), GFP_KERNEL);  in tracing_map_create()
781 	if (!map)  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()
802 	return map;  in tracing_map_create()
804 	tracing_map_destroy(map);  in tracing_map_create()
805 	map = ERR_PTR(-ENOMEM);  in tracing_map_create()
829 int tracing_map_init(struct tracing_map *map)  in tracing_map_init()  argument
833 	if (map->n_fields < 2)  in tracing_map_init()
836 	err = tracing_map_alloc_elts(map);  in tracing_map_init()
840 	tracing_map_clear(map);  in tracing_map_init()
853 	if (memcmp(a->key, b->key, a->elt->map->key_size))  in cmp_entries_dup()
875 	sort_key = &elt_a->map->sort_key;  in cmp_entries_sum()
906 	sort_key = &elt_a->map->sort_key;  in cmp_entries_key()
992 static bool is_key(struct tracing_map *map, unsigned int field_idx)  in is_key()  argument
996 	for (i = 0; i < map->n_keys; i++)  in is_key()
997 		if (map->key_idx[i] == field_idx)  in is_key()
1002 static void sort_secondary(struct tracing_map *map,  in sort_secondary()  argument
1012 	if (is_key(map, primary_key->field_idx))  in sort_secondary()
1017 	if (is_key(map, secondary_key->field_idx))  in sort_secondary()
1038 		set_sort_key(map, secondary_key);  in sort_secondary()
1042 		set_sort_key(map, primary_key);  in sort_secondary()
1074 int tracing_map_sort_entries(struct tracing_map *map,  in tracing_map_sort_entries()  argument
1083 	entries = vmalloc(array_size(sizeof(sort_entry), map->max_elts));  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()
1113 	detect_dups(entries, n_entries, map->key_size);  in tracing_map_sort_entries()
1115 	if (is_key(map, sort_keys[0].field_idx))  in tracing_map_sort_entries()
1120 	set_sort_key(map, &sort_keys[0]);  in tracing_map_sort_entries()
1126 		sort_secondary(map,  in tracing_map_sort_entries()