Re: [PATCH v7 14/20] trace-cmd library: Add logic for in-memory decompression

[Steven Rostedt <rostedt@goodmis.org>]

On Wed, 19 Jan 2022 10:27:09 +0200
"Tzvetomir Stoyanov (VMware)" <tz.stoyanov@gmail.com> wrote:

> There are two approaches to read compressed trace data:
>  - use a temporary file to decompress entire trace data before reading
>  - use in-memory decompression of requested trace data chunk only
> In-memory decompression seems to be more efficient, but selecting which
> approach to use depends in the use case.
> A compression chunk consists of multiple trace pages, that's why a small
> cache with uncompressed chunks is implemented. The chunk stays in the
> cache until there are pages which have reference to it.
> 
> Signed-off-by: Tzvetomir Stoyanov (VMware) <tz.stoyanov@gmail.com>
> ---
>  lib/trace-cmd/trace-input.c | 110 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 110 insertions(+)
> 
> diff --git a/lib/trace-cmd/trace-input.c b/lib/trace-cmd/trace-input.c
> index 45a87a63..f5241e4b 100644
> --- a/lib/trace-cmd/trace-input.c
> +++ b/lib/trace-cmd/trace-input.c
> @@ -29,6 +29,9 @@
>  
>  #define COMMIT_MASK ((1 << 27) - 1)
>  
> +/* force uncompressing in memory */
> +#define INMEMORY_DECOMPRESS
> +
>  /* for debugging read instead of mmap */
>  static int force_read = 0;
>  
> @@ -1257,6 +1260,105 @@ static void free_page_map(struct page_map *page_map)
>  	free(page_map);
>  }
>  
> +#define CHUNK_CHECK_OFFSET(C, O)	((O) >= (C)->offset && (O) < ((C)->offset + (C)->size))

space

> +static struct tracecmd_compress_chunk *get_zchunk(struct cpu_data *cpu, off64_t offset)
> +{
> +	struct cpu_zdata *cpuz = &cpu->compress;
> +	int min, mid, max;
> +
> +	if (!cpuz->chunks)
> +		return NULL;

space

> +	if (offset > (cpuz->chunks[cpuz->count - 1].offset + cpuz->chunks[cpuz->count - 1].size))
> +		return NULL;
> +
> +	/* check if the requested offset is in the last requested chunk or in the next chunk */
> +	if (CHUNK_CHECK_OFFSET(cpuz->chunks + cpuz->last_chunk, offset))
> +		return cpuz->chunks + cpuz->last_chunk;
> +	cpuz->last_chunk++;
> +	if (cpuz->last_chunk < cpuz->count &&
> +	    CHUNK_CHECK_OFFSET(cpuz->chunks + cpuz->last_chunk, offset))
> +		return cpuz->chunks + cpuz->last_chunk;
> +
> +	/* do a binary search to find the chunk holding the given offset */
> +	min = 0;
> +	max = cpuz->count - 1;
> +	mid = (min + max)/2;
> +	while (min <= max) {
> +		if (offset < cpuz->chunks[mid].offset)
> +			max = mid - 1;
> +		else if (offset > (cpuz->chunks[mid].offset + cpuz->chunks[mid].size))
> +			min = mid + 1;
> +		else
> +			break;
> +		mid = (min + max)/2;
> +	}
> +	cpuz->last_chunk = mid;
> +	return cpuz->chunks + mid;

Instead of open coding the above what about:


	struct tracecmd_compress_chunk *chunk;
	struct tracecmd_compress_chunk key;

	key.offset = offset;
	chunk = bsearch(&key, cpuz->chunks, cpuz->count, sizeof(*chunk),
			chunk_cmp);

	if (!chunk) /* should never happen */
		return NULL;

	cpuz->last_chunk = chunk - cpuz->chunks;
	return chunk;
}

static int chunk_cmp(const void *A, const void *B)
{
	struct tracecmd_compress_chunk *a = A;
	struct tracecmd_compress_chunk *b = B;

	if (CHUNK_CHECK_OFFSET(b, a->offset))
		return 0;

	if (b->offset < a->offset)
		return -1;

	return 1;
}
	
> +}
> +
> +static void free_zpage(struct cpu_data *cpu_data, void *map)
> +{
> +	struct zchunk_cache *cache;
> +
> +	list_for_each_entry(cache, &cpu_data->compress.cache, list) {
> +		if (map <= cache->map && map > (cache->map + cache->chunk->size))
> +			goto found;
> +	}
> +	return;
> +
> +found:
> +	cache->ref--;
> +	if (cache->ref)
> +		return;
> +	list_del(&cache->list);
> +	free(cache->map);
> +	free(cache);
> +}
> +
> +static void *read_zpage(struct tracecmd_input *handle, int cpu, off64_t offset)
> +{
> +	struct cpu_data *cpu_data = &handle->cpu_data[cpu];
> +	struct tracecmd_compress_chunk *chunk;
> +	struct zchunk_cache *cache;
> +	void *map = NULL;
> +	int pindex;
> +	int size;
> +
> +	/* Look in the cache of already loaded chunks */
> +	list_for_each_entry(cache, &cpu_data->compress.cache, list) {
> +		if (CHUNK_CHECK_OFFSET(cache->chunk, offset)) {
> +			cache->ref++;
> +			goto out;
> +		}
> +	}
> +
> +	chunk =  get_zchunk(cpu_data, offset);
> +	if (!chunk)
> +		return NULL;

space

> +	size = handle->page_size > chunk->size ? handle->page_size : chunk->size;
> +	map = malloc(size);
> +	if (!map)
> +		return NULL;

space

> +	if (tracecmd_uncompress_chunk(handle->compress, chunk, map) < 0)
> +		goto error;
> +
> +	cache = calloc(1, sizeof(struct zchunk_cache));
> +	if (!cache)
> +		goto error;
> +	cache->ref = 1;
> +	cache->chunk = chunk;
> +	cache->map = map;
> +	list_add(&cache->list, &cpu_data->compress.cache);
> +
> +	/* a chunk can hold multiple pages, get the requested one */
> +out:
> +	pindex = (offset - cache->chunk->offset) / handle->page_size;
> +	return cache->map + (pindex * handle->page_size);
> +error:
> +	free(map);
> +	return NULL;
> +}
> +

-- Steve

>  static void *allocate_page_map(struct tracecmd_input *handle,
>  			       struct page *page, int cpu, off64_t offset)
>  {
> @@ -1268,6 +1370,9 @@ static void *allocate_page_map(struct tracecmd_input *handle,
>  	int ret;
>  	int fd;
>  
> +	if (handle->cpu_compressed && handle->read_zpage)
> +		return read_zpage(handle, cpu, offset);
> +
>  	if (handle->read_page) {
>  		map = malloc(handle->page_size);
>  		if (!map)
> @@ -1410,6 +1515,8 @@ static void __free_page(struct tracecmd_input *handle, struct page *page)
>  
>  	if (handle->read_page)
>  		free(page->map);
> +	else if (handle->read_zpage)
> +		free_zpage(cpu_data, page->map);
>  	else
>  		free_page_map(page->page_map);
>  
> @@ -3954,6 +4061,9 @@ struct tracecmd_input *tracecmd_alloc_fd(int fd, int flags)
>  	/* By default, use usecs, unless told otherwise */
>  	handle->flags |= TRACECMD_FL_IN_USECS;
>  
> +#ifdef INMEMORY_DECOMPRESS
> +	handle->read_zpage = 1;
> +#endif
>  	if (do_read_check(handle, buf, 3))
>  		goto failed_read;
>