Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Simplify handling of fragments in net_buf #52718

Closed
carlescufi opened this issue Dec 1, 2022 · 7 comments · Fixed by #52760
Closed

Simplify handling of fragments in net_buf #52718

carlescufi opened this issue Dec 1, 2022 · 7 comments · Fixed by #52760
Assignees
Labels
area: Bluetooth Host area: Bluetooth area: Networking area: USB Universal Serial Bus Enhancement Changes/Updates/Additions to existing features

Comments

@carlescufi
Copy link
Member

carlescufi commented Dec 1, 2022

Today, fragment support in net_buf uses the frags pointer which is unioned with the node one to save 4 bytes (in a structure of 24 bytes without the optimization).

union {
/** Allow placing the buffer into sys_slist_t */
sys_snode_t node;
/** Fragments associated with this buffer. */
struct net_buf *frags;
};

This forces the net_buf code to provide special net_buf_get and net_buf_put functions instead of being able to call k_fifo_get and k_fifo_put directly:

zephyr/subsys/net/buf.c

Lines 508 to 520 in 1217d85

void net_buf_put(struct k_fifo *fifo, struct net_buf *buf)
{
struct net_buf *tail;
__ASSERT_NO_MSG(fifo);
__ASSERT_NO_MSG(buf);
for (tail = buf; tail->frags; tail = tail->frags) {
tail->flags |= NET_BUF_FRAGS;
}
k_fifo_put_list(fifo, buf, tail);
}

zephyr/subsys/net/buf.c

Lines 412 to 439 in 1217d85

struct net_buf *net_buf_get(struct k_fifo *fifo, k_timeout_t timeout)
#endif
{
struct net_buf *buf, *frag;
NET_BUF_DBG("%s():%d: fifo %p", func, line, fifo);
buf = k_fifo_get(fifo, timeout);
if (!buf) {
return NULL;
}
NET_BUF_DBG("%s():%d: buf %p fifo %p", func, line, buf, fifo);
/* Get any fragments belonging to this buffer */
for (frag = buf; (frag->flags & NET_BUF_FRAGS); frag = frag->frags) {
frag->frags = k_fifo_get(fifo, K_NO_WAIT);
__ASSERT_NO_MSG(frag->frags);
/* The fragments flag is only for FIFO-internal usage */
frag->flags &= ~NET_BUF_FRAGS;
}
/* Mark the end of the fragment list */
frag->frags = NULL;
return buf;
}

This implies that net_buf_get is not atomic when using fragments (although net_buf_put is) which is a problem. It also forces the net_buf layer to duplicate existing k_fifo/lifo APIs due to this behavior. This is because today all fragments are actually placed in the fifo, instead of just the "head" one.

This issue suggests reverting this optimization:

struct net_buf {

		/** Allow placing the buffer into sys_slist_t */
		sys_snode_t node;

		/** Fragments associated with this buffer. */
		struct net_buf *frags;
...

to simplify the code, increase execution speed at the cost of 4 bytes per net_buf.

Important note: this would not constitute an API change, because none of the public APIs would have to be modified at all.

@jfischer-no
Copy link
Collaborator

                            .....                           
                          ......'..                         
                         .,.......''                        
                         .,........''                       
                         .,'........,.                      
                          ''........',                      
                          .,........';.                     
                          .,........':.                     
                           '........':.                     
                           '.......';;                      
                          .'.......';'                      
                         .'........';.                      
                        .''........',                       
                        ''.........',.                      
                       ''..........','                      
                     .''............',,'..                  
                   .,,...............,,,,,,'...........     
                  .,'..............',,,''............'''    
      .'''.......''...............',''''...............''   
     .''.......''................';''''''..............';   
    .............................,:,''''''...........'';;   
    ............................';lc;;,,,,'''''''',,;::;.   
   ............................',;lddollccc:::::cclodd:.    
   ...........................'',;cloc::::;;;;;;:::;;,,,.   
   ...........................'',,:c;,''''.............',.  
   ..........................''',,::,,,,,''...........',:.  
   ..........................''',,:c;,,,,,''......'''',;:.  
   ...........................'',,;ll::::;;,,,,,,,,,,;;:.   
   ...........................'',,,:oollllllllllllcclc,.    
   ...........................''',,:c;;,;,,,''''''''',,.    
   .............'..............''',:;,,,,,'..........','    
   .......''''',,,''''''''.....''',:;,,,,,''........'',,    
    .'''''',,,,;:cc;,,,''''''''''',cc:;;;;,''''''''',;:.    
    .'',,;;;;::ccodoc;,,,,,,'''''',:odolcc:;;;;;;;:::;.     
     .,;:ccloodddddoccc:;,,,,,,,,,;:lollllllllllloo;.       
       ':oool:;'..   .,lcc:;;;;;;;;:c;,,,,''''''',;;.       
         .             .;lollccccc:cc:;,,,''.''''',;.       
                          .';clodddddl::;;,,,,,,;:c;        
                                ....'.';:::cccccc;'         
                                         .',,,,..   

@carlescufi
Copy link
Member Author

@jfischer-no thanks, I guess that means this would be welcome for USB
@jhedberg @jori-nordic any objections for Bluetooth?
@rlubos @jukkar would you OK this for networking?

@rlubos
Copy link
Contributor

rlubos commented Dec 1, 2022

Well, it comes at a cost (networking subsystem RAM consumption increases by 128 bytes only in the default configuration, usually more though as the default buffer count is rather small), but if the processing speed can benefit from this change, I guess we can live with it.

@carlescufi
Copy link
Member Author

Well, it comes at a cost (networking subsystem RAM consumption increases by 128 bytes only in the default configuration, usually more though as the default buffer count is rather small), but if the processing speed can benefit from this change, I guess we can live with it.

Yes, but I don't see how we can maintain the current RAM footprint if we want to achieve atomicity in fragments, aside from reducing complexity.

@jukkar
Copy link
Member

jukkar commented Dec 1, 2022

This proposal LGTM.

@jhedberg
Copy link
Member

jhedberg commented Dec 1, 2022

@jhedberg @jori-nordic any objections for Bluetooth?

I'm ok with it

@jori-nordic
Copy link
Collaborator

okay too

carlescufi added a commit to carlescufi/zephyr that referenced this issue Dec 2, 2022
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves zephyrproject-rtos#52718.

Signed-off-by: Carles Cufi <[email protected]>
jhedberg pushed a commit that referenced this issue Dec 6, 2022
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
theob-pro pushed a commit that referenced this issue Jun 1, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
theob-pro pushed a commit that referenced this issue Jun 2, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
theob-pro pushed a commit that referenced this issue Jun 5, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
theob-pro pushed a commit that referenced this issue Jun 5, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members in
the main net_buf structure. This is done so that both can be used at the
same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever being
inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags in
a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+      +--------+      +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|#2  node|------|#3  node|------|q/slist |
 |node    |      | *flag  | /    | *flag  | /    |        | /    |node    |
 |        |      | frags  |/     | frags  |/     | frags  |/     |        |
 +--------+      +--------+      +--------+      +--------+      +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+       +--------+       +--------+
 |q/slist |-------|#1  node|-------|q/slist |
 |node    |       |        |       |node    |
 |        |       | frags  |       |        |
 +--------+       +--------+       +--------+
                      |            +--------+       +--------+
                      |            |#2  node|--NULL |#3  node|--NULL
                      |            |        |       |        |
                      +------------| frags  |-------| frags  |------NULL
                                   +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
theob-pro pushed a commit that referenced this issue Jun 5, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members
in the main net_buf structure. This is done so that both can be used at
the same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever
being inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags
in a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+     +--------+     +--------+     +--------+     +--------+
 |q/slist |-----|#1  node|-----|#2  node|-----|#3  node|-----|q/slist |
 |node    |     | *flag  | /   | *flag  | /   |        | /   |node    |
 |        |     | frags  |/    | frags  |/    | frags  |/    |        |
 +--------+     +--------+     +--------+     +--------+     +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|q/slist |
 |node    |      |        |      |node    |
 |        |      | frags  |      |        |
 +--------+      +--------+      +--------+
                     |           +--------+       +--------+
                     |           |#2  node|--NULL |#3  node|--NULL
                     |           |        |       |        |
                     +-----------| frags  |-------| frags  |------NULL
                                 +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
theob-pro pushed a commit that referenced this issue Jun 5, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members
in the main net_buf structure. This is done so that both can be used at
the same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever
being inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags
in a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+     +--------+     +--------+     +--------+     +--------+
 |q/slist |-----|#1  node|-----|#2  node|-----|#3  node|-----|q/slist |
 |node    |     | *flag  | /   | *flag  | /   |        | /   |node    |
 |        |     | frags  |/    | frags  |/    | frags  |/    |        |
 +--------+     +--------+     +--------+     +--------+     +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|q/slist |
 |node    |      |        |      |node    |
 |        |      | frags  |      |        |
 +--------+      +--------+      +--------+
                     |           +--------+       +--------+
                     |           |#2  node|--NULL |#3  node|--NULL
                     |           |        |       |        |
                     +-----------| frags  |-------| frags  |------NULL
                                 +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
cfriedt pushed a commit that referenced this issue Jun 6, 2023
This patch reworks how fragments are handled in the net_buf
infrastructure.

In particular, it removes the union around the node and frags members
in the main net_buf structure. This is done so that both can be used at
the same time, at a cost of 4 bytes per net_buf instance.
This implies that the layout of net_buf instances changes whenever
being inserted into a queue (fifo or lifo) or a linked list (slist).

Until now, this is what happened when enqueueing a net_buf with frags
in a queue or linked list:

1.1 Before enqueueing:

 +--------+      +--------+      +--------+
 |#1  node|\     |#2  node|\     |#3  node|\
 |        | \    |        | \    |        | \
 | frags  |------| frags  |------| frags  |------NULL
 +--------+      +--------+      +--------+

net_buf #1 has 2 fragments, net_bufs #2 and #3. Both the node and frags
pointers (they are the same, since they are unioned) point to the next
fragment.

1.2 After enqueueing:

 +--------+     +--------+     +--------+     +--------+     +--------+
 |q/slist |-----|#1  node|-----|#2  node|-----|#3  node|-----|q/slist |
 |node    |     | *flag  | /   | *flag  | /   |        | /   |node    |
 |        |     | frags  |/    | frags  |/    | frags  |/    |        |
 +--------+     +--------+     +--------+     +--------+     +--------+

When enqueing a net_buf (in this case #1) that contains fragments, the
current net_buf implementation actually enqueues all the fragments (in
this case #2 and #3) as actual queue/slist items, since node and frags
are one and the same in memory. This makes the enqueuing operation
expensive and it makes it impossible to atomically dequeue. The `*flag`
notation here means that the `flags` member has been set to
`NET_BUF_FRAGS` in order to be able to reconstruct the frags pointers
when dequeuing.

After this patch, the layout changes considerably:

2.1 Before enqueueing:

 +--------+       +--------+       +--------+
 |#1  node|--NULL |#2  node|--NULL |#3  node|--NULL
 |        |       |        |       |        |
 | frags  |-------| frags  |-------| frags  |------NULL
 +--------+       +--------+       +--------+

This is very similar to 1.1, except that now node and frags are
different pointers, so node is just set to NULL.

2.2 After enqueueing:

 +--------+      +--------+      +--------+
 |q/slist |------|#1  node|------|q/slist |
 |node    |      |        |      |node    |
 |        |      | frags  |      |        |
 +--------+      +--------+      +--------+
                     |           +--------+       +--------+
                     |           |#2  node|--NULL |#3  node|--NULL
                     |           |        |       |        |
                     +-----------| frags  |-------| frags  |------NULL
                                 +--------+       +--------+

When enqueuing net_buf #1, now we only enqueue that very item, instead
of enqueing the frags as well, since now node and frags are separate
pointers. This simplifies the operation and makes it atomic.

Resolves #52718.

Signed-off-by: Carles Cufi <[email protected]>
(cherry picked from commit 3d306c1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area: Bluetooth Host area: Bluetooth area: Networking area: USB Universal Serial Bus Enhancement Changes/Updates/Additions to existing features
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants