[PATCH 1/7] PID namespace translation support

[Dmitry V. Levin]

On Sun, Jul 12, 2020 at 09:46:30PM +0200, Ákos Uzonyi wrote:
[...]
> diff --git a/trie.h b/trie.h
> new file mode 100644
> index 00000000..ef31fd11
> --- /dev/null
> +++ b/trie.h
> @@ -0,0 +1,97 @@
> +/*
> + * Simple trie interface
> + *
> + * Copyright (c) 2020 Ákos Uzonyi <uzonyi.akos at gmail.com>
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: LGPL-2.1-or-later
> + */
> +
> +#ifndef STRACE_TRIE_H
> +#define STRACE_TRIE_H
> +
> +#define TRIE_SET   ((void *) ~(intptr_t) 0)
> +#define TRIE_UNSET ((void *) NULL)
> +
> +#define PTR_BLOCK_SIZE_LG_MAX   24
> +#define DATA_BLOCK_SIZE_LG_MAX  23
> +
> +enum trie_iterate_flags {
> +	TRIE_ITERATE_KEYS_SET   = 1 << 0,
> +	TRIE_ITERATE_KEYS_UNSET = 1 << 1,
> +};
> +
> +/**
> + * Trie control structure.
> + * Trie implemented here has the following properties:
> + *  * It allows storing values of the same size, the size can vary from 1 bit to
> + *    64 bit values (only power of 2 sizes are allowed).
> + *  * The key can be up to 64 bits in size.
> + *  * It has separate configuration for pointer block size and data block size.
> + *  * It can be used for mask storage - supports storing the flag that all keys
> + *    are set/unset in the middle tree layers. See also trie_mask_set() and
> + *    trie_mask_unset().
> + *
> + * How bits of key are used for different block levels:
> + *
> + *     highest bits                                         lowest bits
> + *     | ptr_block_size_lg | ... | < remainder > | data_block_size_lg |
> + *     \______________________________________________________________/
> + *                                 key_size
> + *
> + * So, the remainder is used on the lowest non-data node level.
> + *
> + * As of now, it doesn't implement any mechanisms for resizing/changing key
> + * size.  De-fragmentation is also unsupported currently.
> + */
> +struct trie {
> +	uint64_t set_value;         /**< Default set value */
> +	void *data;
> +	uint8_t item_size_lg;       /**< Item size log2, in bits, 0..6. */
> +	/** Pointer block size log2, in bits. 14-20, usually. */
> +	uint8_t ptr_block_size_lg;
> +	/** Data block size log2, in bits. 11-17, usually. */
> +	uint8_t data_block_size_lg;
> +	uint8_t key_size;           /**< Key size, in bits, 1..64. */
> +};

Please describe what are item size, pointer block size, and data block
size, and how they should be chosen.


-- 
ldv