Linux-Trace-Devel Archive on lore.kernel.org
 help / color / Atom feed
From: Steven Rostedt <rostedt@goodmis.org>
To: "Yordan Karadzhov (VMware)" <y.karadz@gmail.com>
Cc: linux-trace-devel@vger.kernel.org
Subject: Re: [PATCH v2 10/20] kernel-shark: Start using data streams
Date: Fri, 6 Nov 2020 10:18:18 -0500
Message-ID: <20201106101818.77f94a0d@gandalf.local.home> (raw)
In-Reply-To: <d88af9bb-1f15-04cf-230c-ea59b3239931@gmail.com>

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

  reply index

Thread overview: 47+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-10-12 13:35 [PATCH v2 00/20] Start KernelShark v2 transformation Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 01/20] kernel-shark: Start introducing KernelShark 2.0 Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 02/20] kernel-shark: Use only signed types in kshark_entry Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 03/20] kernel-shark: Introduce libkshark-hash Yordan Karadzhov (VMware)
2020-10-12 14:05   ` Steven Rostedt
2020-10-12 14:05     ` Steven Rostedt
2020-10-12 14:18       ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 04/20] kernel-shark: Introduce Data streams Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 05/20] kernel-shark: Add stream_id to kshark_entry Yordan Karadzhov (VMware)
2020-10-13  0:05   ` Steven Rostedt
2020-10-29 10:08     ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 06/20] kernel-shark: Rename static methods in libkshark Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 07/20] kernel-shark: Add basic methods for Data streams Yordan Karadzhov (VMware)
2020-10-13  0:18   ` Steven Rostedt
2020-10-29 10:10     ` Yordan Karadzhov (VMware)
2020-10-29 14:04       ` Steven Rostedt
2020-10-29 14:49         ` Yordan Karadzhov (VMware)
2020-10-30  1:57           ` Steven Rostedt
2020-11-03 13:38             ` Yordan Karadzhov (VMware)
2020-11-04 15:41               ` Steven Rostedt
2020-11-05 14:35                 ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 08/20] kernel-shark: Housekeeping before implementing stream interface Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 09/20] kernel-shark: Add stream interface for trace-cmd data Yordan Karadzhov (VMware)
2020-10-13  0:44   ` Steven Rostedt
2020-10-29 11:16     ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 10/20] kernel-shark: Start using data streams Yordan Karadzhov (VMware)
2020-10-14 18:56   ` Steven Rostedt
2020-11-05 14:58     ` Yordan Karadzhov (VMware)
2020-11-05 18:17       ` Steven Rostedt
2020-11-06 14:31         ` Yordan Karadzhov (VMware)
2020-11-06 15:18           ` Steven Rostedt [this message]
2020-11-09 14:49             ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 11/20] kernel-shark: Remove dead code Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 12/20] kernel-shark: Redesign the plugin interface Yordan Karadzhov (VMware)
2020-10-14 21:09   ` Steven Rostedt
2020-10-12 13:35 ` [PATCH v2 13/20] kernel-shark: Complete the stream integration Yordan Karadzhov (VMware)
2020-10-14 23:52   ` Steven Rostedt
2020-10-12 13:35 ` [PATCH v2 14/20] kernel-shark: Provide merging of multiple data streams Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 15/20] kernel-shark: Integrate the stream definitions with data model Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 16/20] kernel-shark: Use only signed types for model defs Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 17/20] kernel-shark: Add ksmodel_get_bin() Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 18/20] kernel-shark: Protect ksmodel_set_in_range_bining() Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 19/20] kernel-shark: Add methods for time calibration Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 20/20] kernel-shark: Integrate streams with libkshark-configio Yordan Karadzhov (VMware)
2020-11-05 19:22   ` Steven Rostedt
2020-11-09 14:55     ` Yordan Karadzhov (VMware)
2020-11-09 15:28       ` Steven Rostedt

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20201106101818.77f94a0d@gandalf.local.home \
    --to=rostedt@goodmis.org \
    --cc=linux-trace-devel@vger.kernel.org \
    --cc=y.karadz@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-Trace-Devel Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-trace-devel/0 linux-trace-devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-trace-devel linux-trace-devel/ https://lore.kernel.org/linux-trace-devel \
		linux-trace-devel@vger.kernel.org
	public-inbox-index linux-trace-devel

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-trace-devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git