Re: [PATCH v2 10/20] kernel-shark: Start using data streams

[Steven Rostedt <rostedt@goodmis.org>]

On Fri, 6 Nov 2020 16:31:58 +0200
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:

> Hi Steven,
> 
> I am not sure I understand correctly your pseudo-code, so please correct 
> me if my interpretation is wrong.

Note, it's not really pseudo code. I didn't compile it, but it should work
mostly unmodified.

> 
> In the normal case when a new stream is added the corresponding object 
> will be allocated and added to the array of pointers. Later if a stream 
> is removed, instead of freeing the memory we will just manipulate it 
> pointer so that it point to nowhere and this manipulation can be 
> detected by the kshark_is_valid_stream(). Now if we want to add stream 
> again, we will take the broken pointer, will restore its original value 
> and will reuse the object without a new allocations.
> 
> And at the very end we will have to free all pointers (original or 
> manipulated).
> 
> Is this what you are suggesting?

Hmm, let me explain it slightly different, as nothing is "restored".

We change the value of the array from pointer to an index. For ease of
explanation, let's consider this a 32bit machine and we allow 256 streams
(one byte). That is:


sizeof(long) == sizeof(void *) == 4

#define NR_OF_BITS_FOR_STREAM 8

#define KSHARK_INDEX_MASK 0x000000FF
#define KSHARK_INVALID_STREAM 0xFFFFFF00

Lets say we add 4 stream in a row. Each one will detect that free_stream is
equal to n_streams, and just append them to the end of the array
(reallocating the array if necessary). We end up with:


free_stream = 4
n_streams = 4

streams:

  0: 0x07123010   -> stream 1
  1: 0x07123020   -> stream 2
  2: 0x07123030   -> stream 3
  3: 0x07123040   -> stream 4


Now we free stream 3 (at location 2):

free_streams = 2
n_streams = 4

streams:
  0: 0x07123010   -> stream 1
  1: 0x07123020   -> stream 2
  2: 0xFFFFFF04	== (KSHARK_INVALID_MASK | orig:free_streams)
  3: 0x07123040   -> stream 4


Now we free stream 1 (at location 0):

free_streams = 0
n_streams = 4

streams:
  0: 0xFFFFFF02	== (KSHARK_INVALID_MASK | orig:free_streams)
  1: 0x07123020   -> stream 2
  2: 0xFFFFFF04	== (KSHARK_INVALID_MASK | 4)
  3: 0x07123040   -> stream 4


Now lets add stream 5:

free_streams = 2 == (streams[orig:free_streams] & KSHARK_INDEX_MASK)
n_streams = 4

streams:
  0: 0x07123050   -> stream 5
  1: 0x07123020   -> stream 2
  2: 0xFFFFFF04
  3: 0x07123040   -> stream 4

We are just making a link list of free pointers within the array of
streams. This is basically exactly how memory management systems work. The
free memory list is stored inside the memory itself that is being allocated.

The 0xFFFFFF is so that if we want to loop over streams, we can skip the
free slots, by checking: streams[i] & 0xFFFFFF00 != 0xFFFFFF00

Note, the free slots do not point any memory location. Think of the items
in the stream array as:

union {
	struct kshark_stream 	*stream;
	unsigned long		index;
};

You can differentiate without using typecasts with:

	if (streams[i].index & 0xFFFFFF00 == 0xFFFFFF00)
		index = streams[i].index & 0xFF;
	else
		stream = streams[i].stream;

Does that make more sense?

-- Steve