network memory allocator.

From: Evgeniy Polyakov <[email protected]>
Date: Mon, 14 Aug 2006 15:04:03 +0400

include/linux/skbuff.h #endif · line 314

Quoted 3 lines

include/linux/skbuff.h +1 -1

 	/* These elements must be at the end, see alloc_skb() for details.  */
-	unsigned int		truesize;
+	unsigned int		truesize, __tsize;

There is no real need for new member.

net/core/skbuff.c static void skb_release_data(struct sk_b · line 319

Quoted 2 lines

net/core/skbuff.c +1 -1

-		kfree(skb->head);
+		avl_free(skb->head, skb->__tsize);

Just use "skb->end - skb->head + sizeof(struct skb_shared_info)" as the size argument.

Then, there is no reason for skb->__tsize :-)

Design notes.
Original idea was to store meta information used for allocation in an AVL tree [1], but since I found a way to use some "unused" fields in struct page, tree is unused in the allocator.

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Quoted 4 lines · Evgeniy Polyakov

Design notes.
Original idea was to store meta information used for allocation in an AVL tree [1], but since I found a way to use some "unused" fields in struct page, tree is unused in the allocator.

But there seems to be still an AVL tree in there?

Quoted 6 lines

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

So what are its drawbacks compared to slab/kmalloc?

Also if it really performs that much better it might be a good idea to replace all of kmalloc() with it, but doing that would require a lot more benchmarks with various workloads and small and big machines first.

-Andi

Network tree allocator can be used to allocate memory for all network operations from any context....
...
Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

Quoted 6 lines · Evgeniy Polyakov (on Mon, 14 Aug 2006 15:04:03 +0400) wrote:

Network tree allocator can be used to allocate memory for all network operations from any context....
...
Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

Is that true for architectures with virtually indexed caches? How do you avoid the cache aliasing problems?

Quoted 9 lines · Keith Owens

Quoted 6 lines · Evgeniy Polyakov (on Mon, 14 Aug 2006 15:04:03 +0400) wrote:

Network tree allocator can be used to allocate memory for all network operations from any context....
...
Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

Quoted 2 lines

Is that true for architectures with virtually indexed caches? How do you avoid the cache aliasing problems?

Pages are preallocated and stolen from main memory allocator, what is the problem with that caches? Userspace can provide enough offset so that pages would not create aliases - it is usuall mmap.

Now, PA-RISC CPUs have the ability to disable spaceid hashing, and it is entirely possible that the PA-RISC linux port does that, but I thought I would mention it as an example. I'm sure the "official" PA-RISC linux folks can expand on that much much better than I can.

Defragmentation is a part of freeing algorithm and initial fragmentation avoidance is being done at allocation time by removing power-of-two allocations. Rate of fragmentation can be found in some userspace modlling tests being done for both power-of-two SLAB-like and NTA allocators. (more details on project's homepage [4]).

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

Quoted 5 lines · Evgeniy Polyakov

Defragmentation is a part of freeing algorithm and initial fragmentation avoidance is being done at allocation time by removing power-of-two allocations. Rate of fragmentation can be found in some userspace modlling tests being done for both power-of-two SLAB-like and NTA allocators. (more details on project's homepage [4]).

Only with a perfect allocation pattern. And then still only internal fragmentation; your allocator is still vulnerable to external fragmentation - you cannot move allocated chunks around because there are pointers into it, hence you will suffer from external fragmentation.

http://en.wikipedia.org/wiki/Fragmentation_%28computer%29

Quoted 6 lines

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Nice :-)

Quoted 3 lines

Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

I'm still not clear on how you want to do this, only the trivial case of a sniffer was mentioned by you. To be able to do true zero-copy receive each packet will have to have its own page(s). Simply because you do not know the destination before you receive it, the packet could end up going to a whole different socket that the prev/next. As soon as you start packing multiple packets on 1 page, you've lost the zero-copy receive game.

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Quoted 7 lines

I'm still not clear on how you want to do this, only the trivial case of a sniffer was mentioned by you. To be able to do true zero-copy receive each packet will have to have its own page(s). Simply because you do not know the destination before you receive it, the packet could end up going to a whole different socket that the prev/next. As soon as you start packing multiple packets on 1 page, you've lost the zero-copy receive game.

Userspace can sak for next packet and pointer to the new location will be removed.

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Evgeniy Polyakov

Defragmentation is a part of freeing algorithm and initial fragmentation avoidance is being done at allocation time by removing power-of-two allocations. Rate of fragmentation can be found in some userspace modlling tests being done for both power-of-two SLAB-like and NTA allocators. (more details on project's homepage [4]).

Quoted 6 lines

Only with a perfect allocation pattern. And then still only internal fragmentation; your allocator is still vulnerable to external fragmentation - you cannot move allocated chunks around because there are pointers into it, hence you will suffer from external fragmentation.

http://en.wikipedia.org/wiki/Fragmentation_%28computer%29

Nature of network dataflow does not obey to that requirements - all chunks are "short-lives", i.e. sooner or later they will be put back and thus initial region will be repaired.
With existing allocator it never happens by deisgn.

Quoted 13 lines

Quoted 6 lines

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Nice :-)

Quoted 3 lines

Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

Quoted 7 lines

I'm still not clear on how you want to do this, only the trivial case of a sniffer was mentioned by you. To be able to do true zero-copy receive each packet will have to have its own page(s). Simply because you do not know the destination before you receive it, the packet could end up going to a whole different socket that the prev/next. As soon as you start packing multiple packets on 1 page, you've lost the zero-copy receive game.

Userspace can sak for next packet and pointer to the new location will be removed.

Quoted 7 lines

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

Each socket has it's limit, so if allocator got enough memory, blocked sockets will not affect it's behaviour.

Quoted 9 lines

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

Quoted 4 lines

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Ok, not SLAB, but kmaloc/SLAB.

That allocator uses power-of-two allocation, so there is extremely large overhead for several (and in some cases for all) usage cases (e1000 with jumbo frames and unix sockets).

SLAB allows to have chunks of memory from differenct CPU, so it is impossible to create defragmentation, thus kmalloc/SLAB by design will suffer from fragmentation.

Graphs of power-of-two vs. NTA overhead is shown on projects' homepage
- overhead is extremely large.

Quoted 2 lines

Userspace can sak for next packet and pointer to the new location will be removed.

/sak/ask/?

I'm not understanding, if you have a page A with two packets, a and b; once you map that page into user-space that process has access to both packets, which is a security problem. How are you going to solve this?

Also note that zero-copy sending does not have this problem, since data is already grouped by socket.

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

Quoted 5 lines

Quoted 2 lines

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

Each socket has it's limit, so if allocator got enough memory, blocked sockets will not affect it's behaviour.

But isn't the total capacity of the network stack much larger than any allocator can provide?

Quoted 14 lines

Quoted 13 lines

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Quoted 1 line

Ok, not SLAB, but kmaloc/SLAB.

The page-allocator does what you describe, but hardly anybody uses that to store small objects.

Page allocator - buddy allocator, gives out memory in 1<<n pages.

SLAB allocator - uses the page allocator for backing, each SLAB issues objects of a fixed, predetermined size, packed in pages.

kmalloc - uses a collection of SLAB allocators to issue 'variable' size objects (see kmalloc_sizes.h - as you will see internal fragmentation can become quite large for larger objects, but small objects do rather well - and one could always add a frequently used size if it shows to be beneficial).

Quoted 3 lines

That allocator uses power-of-two allocation, so there is extremely large overhead for several (and in some cases for all) usage cases (e1000 with jumbo frames and unix sockets).

Wrong example :-), e1000 is the only driver that doesn't do high order allocs for jumbo frames. But yes, the other drivers should be fixed, relying on higher order allocations is unsound.

Quoted 3 lines

SLAB allows to have chunks of memory from differenct CPU, so it is impossible to create defragmentation, thus kmalloc/SLAB by design will suffer from fragmentation.

*confused* memory is not bound to CPUs other than by NUMA, but even there there is only a single address space.

Quoted 2 lines

Graphs of power-of-two vs. NTA overhead is shown on projects' homepage
- overhead is extremely large.

Yes seen that, but as stated, hardly anybody uses the page allocator to store small objects. However if you do, you get large internal fragmentation but zero external fragmentation (on that allocation level).

This is where my SROG allocator comes in, it is used to group objects by lifetime and returns the pages to the page allocator. This makes the whole allocator short-lived and hence cannot add (external) fragmentation on this level. The use I have for that is that I can then properly gauge how much memory there is available. External fragmentation and guarantees can be difficult to reconcile.

I have no idea how fast/slow the SROG allocator is, and don't really care since its only used as a fallback allocator; what I do care about is determinism (in space).

However, I do have a patch that converts the whole skb layer to use the SROG allocator, not only the payload, so I could do some test. But this is not a serious candidate until all jumbo frame capable drivers have been converted to skb fragments instead of high order allocations - a Good Thing [tm].

Quoted 5 lines · Peter Zijlstra

Quoted 2 lines

Userspace can sak for next packet and pointer to the new location will be removed.

/sak/ask/?

Quoted 3 lines

I'm not understanding, if you have a page A with two packets, a and b; once you map that page into user-space that process has access to both packets, which is a security problem. How are you going to solve this?

Yep, there is such issue.
But no one is ever going to replace socket code with zero-copy interfaces - Linux has backward compatibility noone ever had, so send()/recv() will be there.

It is new interface which can be changed as described in previous e-mails - copy if next chunk belongs to different socket and so on.

Initial user will be sniffer, which should get all packets.

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

Quoted 5 lines

Quoted 2 lines

Each socket has it's limit, so if allocator got enough memory, blocked sockets will not affect it's behaviour.

But isn't the total capacity of the network stack much larger than any allocator can provide?

TCP has 768kb limit on my amd64 with 1gb of ram, so I expect allocator can handle all requests.

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Quoted 14 lines

Quoted 14 lines

Quoted 13 lines

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Quoted 4 lines

Quoted 1 line

Ok, not SLAB, but kmaloc/SLAB.

The page-allocator does what you describe, but hardly anybody uses that to store small objects.

Network stack uses kmalloc.

Quoted 10 lines

Page allocator - buddy allocator, gives out memory in 1<<n pages.

SLAB allocator - uses the page allocator for backing, each SLAB issues objects of a fixed, predetermined size, packed in pages.

kmalloc - uses a collection of SLAB allocators to issue 'variable' size objects (see kmalloc_sizes.h - as you will see internal fragmentation can become quite large for larger objects, but small objects do rather well - and one could always add a frequently used size if it shows to be beneficial).

There is no "frequently used size", kmalloc() does not know what size is frequent and what is not. And there are other mentioned problems with kmalloc/SLAB besides power-of-two, which prevent fragmentation problem resolution.

Quoted 7 lines

Quoted 3 lines

That allocator uses power-of-two allocation, so there is extremely large overhead for several (and in some cases for all) usage cases (e1000 with jumbo frames and unix sockets).

Wrong example :-), e1000 is the only driver that doesn't do high order allocs for jumbo frames. But yes, the other drivers should be fixed, relying on higher order allocations is unsound.

:) do you read netdev@? There are several quite long recent discussions where network hackers blame exactly e1000 for it's hardware problems and ugly memory usage model.
We even think how to change struct sk_buff - Holy Grail of network code
- just to help e1000 driver (well, not exactly for e1000, but that driver was a cause).

Quoted 4 lines

Quoted 3 lines

SLAB allows to have chunks of memory from differenct CPU, so it is impossible to create defragmentation, thus kmalloc/SLAB by design will suffer from fragmentation.

Quoted 2 lines

*confused* memory is not bound to CPUs other than by NUMA, but even there there is only a single address space.

Each slab can have objects allocated in different CPUs, it was done to reduce freeing algorithm. If system wants to defragment several objects into bigger one, it must check all CPUs and find in which cache those objects are placed, which is extremely expensive, so SLAB can not perform defragmentation.

Quoted 7 lines

Quoted 2 lines

Graphs of power-of-two vs. NTA overhead is shown on projects' homepage
- overhead is extremely large.

Yes seen that, but as stated, hardly anybody uses the page allocator to store small objects. However if you do, you get large internal fragmentation but zero external fragmentation (on that allocation level).

Truncated cat /proc/slabinfo on my machine (usual desktop):
size-32 1170 1232 32
size-128 663 780 128
size-64 4239 9558 64

Quoted 11 lines

This is where my SROG allocator comes in, it is used to group objects by lifetime and returns the pages to the page allocator. This makes the whole allocator short-lived and hence cannot add (external) fragmentation on this level. The use I have for that is that I can then properly gauge how much memory there is available. External fragmentation and guarantees can be difficult to reconcile.

I have no idea how fast/slow the SROG allocator is, and don't really care since its only used as a fallback allocator; what I do care about is determinism (in space).

Quoted 5 lines

However, I do have a patch that converts the whole skb layer to use the SROG allocator, not only the payload, so I could do some test. But this is not a serious candidate until all jumbo frame capable drivers have been converted to skb fragments instead of high order allocations - a Good Thing [tm].

You created SROG after my suggestion and discussion about NTA and it works well for it's purpose (doesn't it?), further extension could lead to creation of NTA (or could not).

SROG is a wrapper on top of alloc_pages and list of free objects, there are "several" differencies between allocators and I do not see how they can compete right now.

Quoted 10 lines · Evgeniy Polyakov

Quoted 8 lines · Peter Zijlstra

Quoted 2 lines

Userspace can sak for next packet and pointer to the new location will be removed.

/sak/ask/?

I'm not understanding, if you have a page A with two packets, a and b; once you map that page into user-space that process has access to both packets, which is a security problem. How are you going to solve this?

Quoted 4 lines

Yep, there is such issue.
But no one is ever going to replace socket code with zero-copy interfaces - Linux has backward compatibility noone ever had, so send()/recv() will be there.

The new AIO network API should be able to provide the needed userspace changes.

Quoted 2 lines

It is new interface which can be changed as described in previous e-mails - copy if next chunk belongs to different socket and so on.

But if you copy you're not zero-copy anymore. If you copy every second packet you have a 1/2 copy receive, but not zero.

Quoted 1 line

Initial user will be sniffer, which should get all packets.

Only the root user may get all packets. And most enterprise systems I've seen don't generally run a sniffer. That is usually done by redirecting/copying the data stream in a router and attach a second host to analyse the data.

Quoted 14 lines

Quoted 13 lines

Quoted 10 lines

Quoted 7 lines

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

Each socket has it's limit, so if allocator got enough memory, blocked sockets will not affect it's behaviour.

But isn't the total capacity of the network stack much larger than any allocator can provide?

Quoted 2 lines

TCP has 768kb limit on my amd64 with 1gb of ram, so I expect allocator can handle all requests.

But the capacity of the network stack is larger than this (arbitrary) limit. It is possible to have all 768kb worth of packets stuck on blocked sockets.

Quoted 3 lines

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Growing will not help, the problem is you are out of memory, you cannot grow at that point.

Quoted 14 lines

Quoted 14 lines

Quoted 14 lines

Quoted 13 lines

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Ok, not SLAB, but kmaloc/SLAB.

The page-allocator does what you describe, but hardly anybody uses that to store small objects.

Network stack uses kmalloc.

skbuff_head_cache and skbuff_fclone_cache are SLABs.

Quoted 11 lines

Quoted 10 lines

Page allocator - buddy allocator, gives out memory in 1<<n pages.

SLAB allocator - uses the page allocator for backing, each SLAB issues objects of a fixed, predetermined size, packed in pages.

kmalloc - uses a collection of SLAB allocators to issue 'variable' size objects (see kmalloc_sizes.h - as you will see internal fragmentation can become quite large for larger objects, but small objects do rather well - and one could always add a frequently used size if it shows to be beneficial).

Quoted 4 lines

There is no "frequently used size", kmalloc() does not know what size is frequent and what is not. And there are other mentioned problems with kmalloc/SLAB besides power-of-two, which prevent fragmentation problem resolution.

Yes SLAB is a horrid thing on some points but very good at a lot of other things. But surely there are frequently used sizes, kmalloc will not know, but a developer with profiling tools might.

Quoted 8 lines

Quoted 7 lines

Quoted 3 lines

That allocator uses power-of-two allocation, so there is extremely large overhead for several (and in some cases for all) usage cases (e1000 with jumbo frames and unix sockets).

Wrong example :-), e1000 is the only driver that doesn't do high order allocs for jumbo frames. But yes, the other drivers should be fixed, relying on higher order allocations is unsound.

Quoted 6 lines

:) do you read netdev@? There are several quite long recent discussions where network hackers blame exactly e1000 for it's hardware problems and ugly memory usage model.
We even think how to change struct sk_buff - Holy Grail of network code
- just to help e1000 driver (well, not exactly for e1000, but that driver was a cause).

Have you seen the latest code? It allocates single pages and puts them in the skb_shared_info fragments. Surely it might have been the one pushing for these changes, but they are done. Current status.

Quoted 7 lines

Quoted 6 lines

Quoted 3 lines

SLAB allows to have chunks of memory from differenct CPU, so it is impossible to create defragmentation, thus kmalloc/SLAB by design will suffer from fragmentation.

*confused* memory is not bound to CPUs other than by NUMA, but even there there is only a single address space.

Quoted 5 lines

Each slab can have objects allocated in different CPUs, it was done to reduce freeing algorithm. If system wants to defragment several objects into bigger one, it must check all CPUs and find in which cache those objects are placed, which is extremely expensive, so SLAB can not perform defragmentation.

What you are referring to is coalescence, and yes coalescing over page boundaries is hard in the SLAB layer, the page allocator does that.

Quoted 8 lines

Quoted 7 lines

Quoted 2 lines

Graphs of power-of-two vs. NTA overhead is shown on projects' homepage
- overhead is extremely large.

Yes seen that, but as stated, hardly anybody uses the page allocator to store small objects. However if you do, you get large internal fragmentation but zero external fragmentation (on that allocation level).

Quoted 4 lines

Truncated cat /proc/slabinfo on my machine (usual desktop):
size-32 1170 1232 32
size-128 663 780 128
size-64 4239 9558 64

Sure, point being?

size-64 4497 4602 64 59 1 : tunables 120 60
8 : slabdata 78 78 0

4497 objects used out of 4602 available, object size 64 bytes, 59 objects per slab of 1 page. .... 78 pages with active objects out of 78 pages allocated.

Quoted 17 lines

Quoted 11 lines

This is where my SROG allocator comes in, it is used to group objects by lifetime and returns the pages to the page allocator. This makes the whole allocator short-lived and hence cannot add (external) fragmentation on this level. The use I have for that is that I can then properly gauge how much memory there is available. External fragmentation and guarantees can be difficult to reconcile.

I have no idea how fast/slow the SROG allocator is, and don't really care since its only used as a fallback allocator; what I do care about is determinism (in space).

Quoted 5 lines

However, I do have a patch that converts the whole skb layer to use the SROG allocator, not only the payload, so I could do some test. But this is not a serious candidate until all jumbo frame capable drivers have been converted to skb fragments instead of high order allocations - a Good Thing [tm].

Quoted 3 lines

You created SROG after my suggestion and discussion about NTA and it works well for it's purpose (doesn't it?), further extension could lead to creation of NTA (or could not).

I started with a very broken in-situ allocator (that tried to do the same thing) in the very first patch. It was only later that I realised the full extend of the skbuff requirements.

And no, NTA is too complex an allocator to do what I need. And more specifically its design is quite contrary to what I have done. I create/destroy an allocator instance per packet, you have one allocator instance and serve multiple packets.

Quoted 3 lines

SROG is a wrapper on top of alloc_pages and list of free objects, there are "several" differencies between allocators and I do not see how they can compete right now.

Yes allocators are build in layers, the page allocator the the basic building block in Linux.

Quoted 16 lines · Peter Zijlstra

Quoted 14 lines · Evgeniy Polyakov

Quoted 8 lines · Peter Zijlstra

Quoted 2 lines

Userspace can sak for next packet and pointer to the new location will be removed.

/sak/ask/?

I'm not understanding, if you have a page A with two packets, a and b; once you map that page into user-space that process has access to both packets, which is a security problem. How are you going to solve this?

Yep, there is such issue.
But no one is ever going to replace socket code with zero-copy interfaces - Linux has backward compatibility noone ever had, so send()/recv() will be there.

Quoted 2 lines

The new AIO network API should be able to provide the needed userspace changes.

Kevent based network AIO already handle it.
This changes are different.

Quoted 8 lines

Quoted 2 lines

It is new interface which can be changed as described in previous e-mails - copy if next chunk belongs to different socket and so on.

But if you copy you're not zero-copy anymore. If you copy every second packet you have a 1/2 copy receive, but not zero.

Quoted 1 line

Initial user will be sniffer, which should get all packets.

Quoted 4 lines

Only the root user may get all packets. And most enterprise systems I've seen don't generally run a sniffer. That is usually done by redirecting/copying the data stream in a router and attach a second host to analyse the data.

Nice words. And what "second host" is supposed to do with that traffic? I expect it should not be Linux (not an "enterprise system"?). WIll it copy to userspace or have some kind of a zero-copy?

Quoted 14 lines

Quoted 14 lines

Quoted 13 lines

Quoted 10 lines

Quoted 7 lines

Quoted 4 lines

As described in recent threads [3] it is also possible to eliminate any kind of main system OOM influence on network dataflow processing, thus it is possible to prevent deadlock for systems, which use network as memory storage (swap over network, iSCSI, NBD and so on).

How? You have never stated how you will avoid getting all packets stuck in blocked sockets.

Each socket has it's limit, so if allocator got enough memory, blocked sockets will not affect it's behaviour.

But isn't the total capacity of the network stack much larger than any allocator can provide?

Quoted 6 lines

Quoted 2 lines

TCP has 768kb limit on my amd64 with 1gb of ram, so I expect allocator can handle all requests.

But the capacity of the network stack is larger than this (arbitrary) limit. It is possible to have all 768kb worth of packets stuck on blocked sockets.

And so what?

You said, that separated from main allocator can not handle all memory requests being done by the stack, as you can see it easily can.

Quoted 4 lines

Quoted 3 lines

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Quoted 2 lines

Growing will not help, the problem is you are out of memory, you cannot grow at that point.

You do not see the point of network tree allocator.

It can live with main system OOM since it has preallocated separate pool, which can be increased when there is a requirement for that, for example when system is not in OOM.

Quoted 19 lines

Quoted 19 lines

Quoted 18 lines

Quoted 9 lines

Quoted 9 lines

On another note, I think you misunderstand our SLAB allocator; we do not round up to nearest order page alloc per object; SLAB is build to avoid that and is designed to pack equal size objects into pages. The kmalloc allocator is build on top of several SLAB allocators; each with its specific size objects to serve.

For example, the 64 byte SLAB will serve 64 byte objects, and packs about PAGE_SIZE/64 per page (about since there is some overhead).

Quoted 6 lines

Quoted 4 lines

So the actual internal fragmentation of the current kmalloc/SLAB allocator is not as bad as you paint it. The biggest problem we have with the SLAB thing is getting pages back from it. (And the horrific complexity of the current implementation)

Ok, not SLAB, but kmaloc/SLAB.

The page-allocator does what you describe, but hardly anybody uses that to store small objects.

Quoted 3 lines

Quoted 1 line

Network stack uses kmalloc.

skbuff_head_cache and skbuff_fclone_cache are SLABs.

It is quite small part of the stack, isn't it?
And btw, they still suffer from SLAB design, since it is possibly to get another smaller object right after all skbs are allocated from given page. It is a minor thing of course, but nevertheless worh mentioning.

Quoted 16 lines

Quoted 15 lines

Quoted 10 lines

Page allocator - buddy allocator, gives out memory in 1<<n pages.

SLAB allocator - uses the page allocator for backing, each SLAB issues objects of a fixed, predetermined size, packed in pages.

kmalloc - uses a collection of SLAB allocators to issue 'variable' size objects (see kmalloc_sizes.h - as you will see internal fragmentation can become quite large for larger objects, but small objects do rather well - and one could always add a frequently used size if it shows to be beneficial).

There is no "frequently used size", kmalloc() does not know what size is frequent and what is not. And there are other mentioned problems with kmalloc/SLAB besides power-of-two, which prevent fragmentation problem resolution.

Quoted 3 lines

Yes SLAB is a horrid thing on some points but very good at a lot of other things. But surely there are frequently used sizes, kmalloc will not know, but a developer with profiling tools might.

Does not scale - admin must run system under profiling, add new entries into kmalloc_sizes.h recompile the kernel... No way.

Quoted 15 lines

Quoted 14 lines

Quoted 7 lines

Quoted 3 lines

That allocator uses power-of-two allocation, so there is extremely large overhead for several (and in some cases for all) usage cases (e1000 with jumbo frames and unix sockets).

Wrong example :-), e1000 is the only driver that doesn't do high order allocs for jumbo frames. But yes, the other drivers should be fixed, relying on higher order allocations is unsound.

:) do you read netdev@? There are several quite long recent discussions where network hackers blame exactly e1000 for it's hardware problems and ugly memory usage model.
We even think how to change struct sk_buff - Holy Grail of network code
- just to help e1000 driver (well, not exactly for e1000, but that driver was a cause).

Quoted 3 lines

Have you seen the latest code? It allocates single pages and puts them in the skb_shared_info fragments. Surely it might have been the one pushing for these changes, but they are done. Current status.

Plese check e1000_alloc_rx_buffers() function and rx_buffer_len value. You are wrong.

Quoted 13 lines

Quoted 12 lines

Quoted 6 lines

Quoted 3 lines

SLAB allows to have chunks of memory from differenct CPU, so it is impossible to create defragmentation, thus kmalloc/SLAB by design will suffer from fragmentation.

*confused* memory is not bound to CPUs other than by NUMA, but even there there is only a single address space.

Each slab can have objects allocated in different CPUs, it was done to reduce freeing algorithm. If system wants to defragment several objects into bigger one, it must check all CPUs and find in which cache those objects are placed, which is extremely expensive, so SLAB can not perform defragmentation.

Quoted 2 lines

What you are referring to is coalescence, and yes coalescing over page boundaries is hard in the SLAB layer, the page allocator does that.

Page boundaries is only minor part of the problem.
Objects from the same page can live in different (per-cpu) SLAB caches.

Quoted 18 lines

Quoted 8 lines

Quoted 7 lines

Quoted 2 lines

Graphs of power-of-two vs. NTA overhead is shown on projects' homepage
- overhead is extremely large.

Yes seen that, but as stated, hardly anybody uses the page allocator to store small objects. However if you do, you get large internal fragmentation but zero external fragmentation (on that allocation level).

Quoted 4 lines

Truncated cat /proc/slabinfo on my machine (usual desktop):
size-32 1170 1232 32
size-128 663 780 128
size-64 4239 9558 64

Sure, point being?

size-64 4497 4602 64 59 1 : tunables 120 60
8 : slabdata 78 78 0

Quoted 3 lines

4497 objects used out of 4602 available, object size 64 bytes, 59 objects per slab of 1 page. .... 78 pages with active objects out of 78 pages allocated.

It was your words quoted above that "hardly anybody uses the page allocator to store small objects", as you can see, there are quite a few of them allocated through kmalloc but not through kmem_cache.

Quoted 34 lines

Quoted 17 lines

Quoted 11 lines

This is where my SROG allocator comes in, it is used to group objects by lifetime and returns the pages to the page allocator. This makes the whole allocator short-lived and hence cannot add (external) fragmentation on this level. The use I have for that is that I can then properly gauge how much memory there is available. External fragmentation and guarantees can be difficult to reconcile.

I have no idea how fast/slow the SROG allocator is, and don't really care since its only used as a fallback allocator; what I do care about is determinism (in space).

Quoted 5 lines

However, I do have a patch that converts the whole skb layer to use the SROG allocator, not only the payload, so I could do some test. But this is not a serious candidate until all jumbo frame capable drivers have been converted to skb fragments instead of high order allocations - a Good Thing [tm].

Quoted 3 lines

You created SROG after my suggestion and discussion about NTA and it works well for it's purpose (doesn't it?), further extension could lead to creation of NTA (or could not).

I started with a very broken in-situ allocator (that tried to do the same thing) in the very first patch. It was only later that I realised the full extend of the skbuff requirements.

And no, NTA is too complex an allocator to do what I need. And more specifically its design is quite contrary to what I have done. I create/destroy an allocator instance per packet, you have one allocator instance and serve multiple packets.

Quoted 3 lines

SROG is a wrapper on top of alloc_pages and list of free objects, there are "several" differencies between allocators and I do not see how they can compete right now.

Quoted 2 lines

Yes allocators are build in layers, the page allocator the the basic building block in Linux.

Ok, it's your point.
Actum est, ilicet.

Quoted 20 lines · Evgeniy Polyakov

Quoted 18 lines · Peter Zijlstra

Quoted 6 lines · Evgeniy Polyakov

Quoted 5 lines · Peter Zijlstra

Quoted 2 lines

Userspace can sak for next packet and pointer to the new location will be removed.

/sak/ask/?

Quoted 8 lines

Quoted 3 lines

I'm not understanding, if you have a page A with two packets, a and b; once you map that page into user-space that process has access to both packets, which is a security problem. How are you going to solve this?

Yep, there is such issue.
But no one is ever going to replace socket code with zero-copy interfaces - Linux has backward compatibility noone ever had, so send()/recv() will be there.

The new AIO network API should be able to provide the needed userspace changes.

Quoted 2 lines

Kevent based network AIO already handle it.
This changes are different.

You said you couldn't do zero-copy because the userspace interface didn't allow it.
I assume the network AIO interface does, but still you have your initial allocation problem, one cannot put more than 1 packet on each page.

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

TCP has 768kb limit on my amd64 with 1gb of ram, so I expect allocator can handle all requests.

But the capacity of the network stack is larger than this (arbitrary) limit. It is possible to have all 768kb worth of packets stuck on blocked sockets.

And so what?

Well, if all packets are stuck, you have a dead system.

Quoted 3 lines

You said, that separated from main allocator can not handle all memory requests being done by the stack, as you can see it easily can.

It could if you can provide adequate detection of memory pressure and fallback to a degraded mode within the same allocator/stack and can guarantee limited service to critical parts.

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Quoted 8 lines

Quoted 2 lines

Growing will not help, the problem is you are out of memory, you cannot grow at that point.

You do not see the point of network tree allocator.

It can live with main system OOM since it has preallocated separate pool, which can be increased when there is a requirement for that, for example when system is not in OOM.

It cannot increase enough, ever. The total capacity of the network stack is huge.
And the sole problem I'm addressing is getting the system to work reliably in tight memory situations, that is during reclaim; one cannot decide to grow then, nor postpone, too late.

Quoted 6 lines

Quoted 1 line

skbuff_head_cache and skbuff_fclone_cache are SLABs.

It is quite small part of the stack, isn't it?
And btw, they still suffer from SLAB design, since it is possibly to get another smaller object right after all skbs are allocated from given page. It is a minor thing of course, but nevertheless worh mentioning.

Small but crucial, that is why I've been replacing all.

Quoted 6 lines

Quoted 3 lines

Yes SLAB is a horrid thing on some points but very good at a lot of other things. But surely there are frequently used sizes, kmalloc will not know, but a developer with profiling tools might.

Does not scale - admin must run system under profiling, add new entries into kmalloc_sizes.h recompile the kernel... No way.

s/admin/developer/
It has been the way so far.

Quoted 2 lines

Plese check e1000_alloc_rx_buffers() function and rx_buffer_len value. You are wrong.

e1000_alloc_rx_buffers_ps()

but it does not take away that any card/driver that does depend on higher order allocations is unreliable.

Kevent network AIO is completely different from network tree allocator.

So network allocator reserves above megabyte and works with it in a smart way (without too much overhead).
Then system goes into OOM and requires to swap a page, which notification was sent to remote swap storage.
Swap storage then sends an ack for that data, since network allocations are separated from main system ones, network allocator easily gets 60 (or 4k, since it has a reserve, which exeeds maximum allowed TCP memory limit) bytes for ack and process than notification thus "freeing" acked data and main system can work with that free memory.
No need to detect OOM or something other - it just works.

I expect you will give me an example, when all above megabyte is going to be stuck somewhere.
But... If it is not acked, each new packet goes slow path since VJ header prediction fails and falls into memory limit check which will drop that packet immediately without event trying to select a socket.

Quoted 13 lines

Quoted 12 lines

Quoted 6 lines

Quoted 3 lines

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Growing will not help, the problem is you are out of memory, you cannot grow at that point.

You do not see the point of network tree allocator.

It can live with main system OOM since it has preallocated separate pool, which can be increased when there is a requirement for that, for example when system is not in OOM.

Quoted 5 lines

It cannot increase enough, ever. The total capacity of the network stack is huge.
And the sole problem I'm addressing is getting the system to work reliably in tight memory situations, that is during reclaim; one cannot decide to grow then, nor postpone, too late.

Network *is* limited, it is not terabyte array which is going to be placed into VFS cache.

Quoted 8 lines

Quoted 6 lines

Quoted 1 line

skbuff_head_cache and skbuff_fclone_cache are SLABs.

It is quite small part of the stack, isn't it?
And btw, they still suffer from SLAB design, since it is possibly to get another smaller object right after all skbs are allocated from given page. It is a minor thing of course, but nevertheless worh mentioning.

Small but crucial, that is why I've been replacing all.

Sigh, replace kmem_cache_alloc() with avl_alloc() - it does not matter.

Quoted 9 lines

Quoted 6 lines

Quoted 3 lines

Yes SLAB is a horrid thing on some points but very good at a lot of other things. But surely there are frequently used sizes, kmalloc will not know, but a developer with profiling tools might.

Does not scale - admin must run system under profiling, add new entries into kmalloc_sizes.h recompile the kernel... No way.

s/admin/developer/
It has been the way so far.

Could you say what are preferred sizes in my testing machines here? :) For example MMIO-read based chips (excellent realtek 8139 adapter) can allocate not only 1500 bytes of memory, but real size of received frame. I even used it for receiving zero-copy (really excellent hardware for it's price) into VFS cache implementation (without any kind of page-per-packet stuff), but it is not related to our discussion.

Have you seen how many adapters support packet split?

Quoted 1 line · Evgeniy Polyakov

Kevent network AIO is completely different from network tree allocator.

How can that be? packets still need to be received, yes?

Quoted 11 lines

So network allocator reserves above megabyte and works with it in a smart way (without too much overhead).
Then system goes into OOM and requires to swap a page, which notification was sent to remote swap storage.
Swap storage then sends an ack for that data, since network allocations are separated from main system ones, network allocator easily gets 60 (or 4k, since it has a reserve, which exeeds maximum allowed TCP memory limit) bytes for ack and process than notification thus "freeing" acked data and main system can work with that free memory.
No need to detect OOM or something other - it just works.

Quoted 5 lines

I expect you will give me an example, when all above megabyte is going to be stuck somewhere.
But... If it is not acked, each new packet goes slow path since VJ header prediction fails and falls into memory limit check which will drop that packet immediately without event trying to select a socket.

Not sure on the details; but you say: when we reach the threshold all following packets will be dropped. So if you provide enough memory to exceed the limit, you have some extra. If you then use that extra bit to allow ACKs to pass through, then you're set.

Sounds good, but you'd have to carve a path for the ACKs, right? Or is that already there?

Also, I'm worried with the effects of external fragmentation esp. after long run times. Analysing non trivial memory allocators is hard, very often too hard.

Quoted 19 lines

Quoted 18 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

And there is a simple task in TODO list to dynamically grow cache when threshold of memory is in use. It is really simple task and will be implemented as soon as I complete suggestions mentioned by Andrew Morton.

Quoted 8 lines

Quoted 2 lines

Growing will not help, the problem is you are out of memory, you cannot grow at that point.

You do not see the point of network tree allocator.

It can live with main system OOM since it has preallocated separate pool, which can be increased when there is a requirement for that, for example when system is not in OOM.

It cannot increase enough, ever. The total capacity of the network stack is huge.
And the sole problem I'm addressing is getting the system to work reliably in tight memory situations, that is during reclaim; one cannot decide to grow then, nor postpone, too late.

Quoted 2 lines

Network *is* limited, it is not terabyte array which is going to be placed into VFS cache.

No it is not, but you bound it.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

Quoted 1 line

skbuff_head_cache and skbuff_fclone_cache are SLABs.

It is quite small part of the stack, isn't it?
And btw, they still suffer from SLAB design, since it is possibly to get another smaller object right after all skbs are allocated from given page. It is a minor thing of course, but nevertheless worh mentioning.

Quoted 3 lines

Quoted 1 line

Small but crucial, that is why I've been replacing all.

Sigh, replace kmem_cache_alloc() with avl_alloc() - it does not matter.

It does matter, you need the whole packet, if you cannot allocate a sk_buff you're still stuck.

Quoted 10 lines

Quoted 9 lines

Quoted 6 lines

Quoted 3 lines

Yes SLAB is a horrid thing on some points but very good at a lot of other things. But surely there are frequently used sizes, kmalloc will not know, but a developer with profiling tools might.

Does not scale - admin must run system under profiling, add new entries into kmalloc_sizes.h recompile the kernel... No way.

s/admin/developer/
It has been the way so far.

Quoted 6 lines

Could you say what are preferred sizes in my testing machines here? :) For example MMIO-read based chips (excellent realtek 8139 adapter) can allocate not only 1500 bytes of memory, but real size of received frame. I even used it for receiving zero-copy (really excellent hardware for it's price) into VFS cache implementation (without any kind of page-per-packet stuff), but it is not related to our discussion.

Well generally the developer of the driver can say, and very often it just doesn't matter, but see the wide spread use of private SLABs to see there is benefit in manually tuning stuff.

Quoted 11 lines

Quoted 11 lines

So network allocator reserves above megabyte and works with it in a smart way (without too much overhead).
Then system goes into OOM and requires to swap a page, which notification was sent to remote swap storage.
Swap storage then sends an ack for that data, since network allocations are separated from main system ones, network allocator easily gets 60 (or 4k, since it has a reserve, which exeeds maximum allowed TCP memory limit) bytes for ack and process than notification thus "freeing" acked data and main system can work with that free memory.
No need to detect OOM or something other - it just works.

Quoted 5 lines

Quoted 5 lines

I expect you will give me an example, when all above megabyte is going to be stuck somewhere.
But... If it is not acked, each new packet goes slow path since VJ header prediction fails and falls into memory limit check which will drop that packet immediately without event trying to select a socket.

I mean without trying to queue data into socket.

Quoted 5 lines

Not sure on the details; but you say: when we reach the threshold all following packets will be dropped. So if you provide enough memory to exceed the limit, you have some extra. If you then use that extra bit to allow ACKs to pass through, then you're set.

Quoted 2 lines

Sounds good, but you'd have to carve a path for the ACKs, right? Or is that already there?

Acks with or without attached data are processed before data queueing. See tcp_rcv_established().

Quoted 7 lines

Not sure on the details; but you say: when we reach the threshold all following packets will be dropped. So if you provide enough memory to exceed the limit, you have some extra. If you then use that extra bit to allow ACKs to pass through, then you're set.

Sounds good, but you'd have to carve a path for the ACKs, right? Or is that already there?

Acks with or without attached data are processed before data queueing. See tcp_rcv_established().

Right, however I just realised that most storage protocols (level 7) have their own ACK msgs and do not rely on TCP (level 4) ACKs like this.

So I would like to come back on this, I do need a full data channel open.

Quoted 3 lines · Peter Zijlstra

It could if you can provide adequate detection of memory pressure and fallback to a degraded mode within the same allocator/stack and can guarantee limited service to critical parts.

It is not needed, since network allocations are separated from main system ones.
I think I need to show an example here.

Let's main system works only with TCP for simplicity. Let's maximum allowed memory is limited by 1mb (it is 768k on machine with 1gb of ram).

Quoted 3 lines

Let's main system works only with TCP for simplicity. Let's maximum allowed memory is limited by 1mb (it is 768k on machine with 1gb of ram).

The maximum amount of memory available for TCP on a system with 1 GB of memory is 768 MB (not 768 KB).

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Quoted 6 lines

Benchmarks with trivial epoll based web server showed noticeble (more than 40%) imrovements of the request rates (1600-1800 requests per second vs. more than 2300 ones). It can be described by more cache-friendly freeing algorithm, by tighter objects packing and thus reduced cache line ping-pongs, reduced lookups into higher-layer caches and so on.

Is that an hypothesis, or did you get a chance to gather cache stats with something like http://www.hp.com/go/Caliper or the like on the platform(s) you were testing?

rick jones

Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

net/core/alloc/avl.c new file +4 -0

+static inline void avl_set_left(struct avl_node *node, avl_t val)
+{
+	node->left = val;
+}

net/core/alloc/avl.c new file +70 -0

+static inline void avl_rotate_complete(struct avl_node *parent, struct avl_node *node, int cpu)
+{
+	avl_set_parent(node, parent->parent);
+	if (parent->parent != AVL_NODE_EMPTY) {
+		if (parent->pos == AVL_RIGHT)
+			avl_set_right(avl_get_node(parent->parent, cpu), node->id);
+		else
+			avl_set_left(avl_get_node(parent->parent, cpu), node->id);
+	}
+	avl_set_parent(parent, node->id);
+}
+
+static inline void avl_ll(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *left = avl_get_node(node->left, cpu);
+	
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_left(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_LEFT;
+	if (!left) {
+		avl_set_right(parent, AVL_NODE_EMPTY);
+	} else {
+		avl_set_parent(left, parent->id);
+		left->pos = AVL_RIGHT;
+		avl_set_right(parent, left->id);
+	}
+}
+
+static inline void avl_rr(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *right = avl_get_node(node->right, cpu);
+
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_right(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_RIGHT;
+	if (!right)
+		avl_set_left(parent, AVL_NODE_EMPTY);
+	else {
+		avl_set_parent(right, parent->id);
+		right->pos = AVL_LEFT;
+		avl_set_left(parent, right->id);
+	}
+}
+
+static inline void avl_rl_balance(struct avl_node *node, int cpu)
+{
+	avl_rr(node, cpu);
+	avl_ll(node, cpu);
+}
+
+static inline void avl_lr_balance(struct avl_node *node, int cpu)
+{
+	avl_ll(node, cpu);
+	avl_rr(node, cpu);
+}
+
+static inline void avl_balance_single(struct avl_node *node, struct avl_node *parent)
+{
+	node->balance = parent->balance = AVL_BALANCED;
+}
+
+static inline void avl_ll_balance(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+
+	avl_ll(node, cpu);

There will be heaps of cacheline pingpong accessing these arrays. I'd have though that

static struct whatever {
	avl_t avl_node_id;
	struct avl_node **avl_node_array;
	struct list_head *avl_container_array;
	struct avl_node *avl_root;
	struct avl_free_list *avl_free_list_head;
	spinlock_t avl_free_lock;
} __cacheline_aligned_in_smp whatevers[NR_CPUS];

would be better.

Quoted 13 lines · Andrew Morton

There will be heaps of cacheline pingpong accessing these arrays. I'd have though that

static struct whatever {
	avl_t avl_node_id;
	struct avl_node **avl_node_array;
	struct list_head *avl_container_array;
	struct avl_node *avl_root;
	struct avl_free_list *avl_free_list_head;
	spinlock_t avl_free_lock;
} __cacheline_aligned_in_smp whatevers[NR_CPUS];

Quoted 1 line

would be better.

Or even better per cpu data. New global/static NR_CPUS arrays should be really discouraged.

-Andi

I had a version with per-cpu data - it is not very convenient to use here with it's per_cpu_ptr dereferencings....

Quoted 4 lines · On Mon, 14 Aug 2006 15:04:03 +0400 Evgeniy Polyakov <[email protected]> wrote:

Design of allocator allows to map all node's pages into userspace thus allows to have true zero-copy support for both sending and receiving dataflows.

If the pages can be order-1 or higher then they'll need to be compound pages so that the kernel gets the page's refcounting correct if the user tries to perform direct-io against them (get_user_pages()).

And compound pages use ->lru for internal metadata - see prep_compound_page().

net/core/alloc/avl.c line 51

Quoted 6 lines

net/core/alloc/avl.c new file +6 -0

+static avl_t avl_node_id[NR_CPUS];
+static struct avl_node **avl_node_array[NR_CPUS];
+static struct list_head *avl_container_array[NR_CPUS];
+static struct avl_node *avl_root[NR_CPUS];
+static struct avl_free_list *avl_free_list_head[NR_CPUS];
+static spinlock_t avl_free_lock[NR_CPUS];

There will be heaps of cacheline pingpong accessing these arrays. I'd have though that

static struct whatever {
	avl_t avl_node_id;
	struct avl_node **avl_node_array;
	struct list_head *avl_container_array;
	struct avl_node *avl_root;
	struct avl_free_list *avl_free_list_head;
	spinlock_t avl_free_lock;
} __cacheline_aligned_in_smp whatevers[NR_CPUS];

would be better.

net/core/alloc/avl.h line 42

Quoted 2 lines

net/core/alloc/avl.h new file +2 -0

+typedef unsigned long value_t;
+typedef u16 avl_t;

Do we really need the typedefs?

If so, these have too generic names for globally-scoped identifiers.

Quoted 6 lines

net/core/alloc/avl.c new file +6 -0

+static inline struct avl_node *avl_get_node(avl_t id, int cpu)
+{
+	avl_t idx, off;
+
+	if (id >= AVL_NODE_NUM)
+		return NULL;

net/core/alloc/avl.c line 64

Quoted 6 lines

net/core/alloc/avl.c new file +6 -0

+	
+	idx = id/AVL_NODES_ON_PAGE;
+	off = id%AVL_NODES_ON_PAGE;
+
+	return &(avl_node_array[cpu][idx][off]);
+}

Too big to inline.

net/core/alloc/avl.c line 72

Quoted 7 lines

net/core/alloc/avl.c new file +7 -0

+static inline struct avl_node *avl_get_node_ptr(unsigned long ptr)
+{
+	struct page *page = virt_to_page(ptr);
+	struct avl_node *node = (struct avl_node *)(page->lru.next);
+
+	return node;
+}

Probably OK.

net/core/alloc/avl.c line 83

Quoted 10 lines

net/core/alloc/avl.c new file +10 -0

+static inline void avl_set_node_ptr(unsigned long ptr, struct avl_node *node, int order)
+{
+	int nr_pages = 1<<order, i;
+	struct page *page = virt_to_page(ptr);
+	
+	for (i=0; i<nr_pages; ++i) {
+		page->lru.next = (void *)node;
+		page++;
+	}
+}

Too big

net/core/alloc/avl.c line 91

Quoted 7 lines

net/core/alloc/avl.c new file +7 -0

+static inline int avl_get_cpu_ptr(unsigned long ptr)
+{
+	struct page *page = virt_to_page(ptr);
+	int cpu = (int)(unsigned long)(page->lru.prev);
+
+	return cpu;
+}

Too big

Quoted 4 lines

net/core/alloc/avl.c new file +4 -0

+static inline void avl_set_cpu_ptr(unsigned long ptr, int cpu, int order)
+{
+	int nr_pages = 1<<order, i;
+	struct page *page = virt_to_page(ptr);

net/core/alloc/avl.c line 102

Quoted 6 lines

net/core/alloc/avl.c new file +6 -0

+			
+	for (i=0; i<nr_pages; ++i) {
+		page->lru.prev = (void *)(unsigned long)cpu;
+		page++;
+	}
+}

Too big

net/core/alloc/avl.c line 112

Quoted 9 lines

net/core/alloc/avl.c new file +9 -0

+static inline enum avl_balance avl_compare(struct avl_node *a, struct avl_node *b)
+{
+	if (a->value == b->value)
+		return AVL_BALANCED;
+	else if (a->value > b->value)
+		return AVL_RIGHT;
+	else
+		return AVL_LEFT;
+}

Might be too big.

Quoted 4 lines

net/core/alloc/avl.c new file +4 -0

+static inline void avl_set_left(struct avl_node *node, avl_t val)
+{
+	node->left = val;
+}

net/core/alloc/avl.c line 127

Quoted 10 lines

net/core/alloc/avl.c new file +10 -0

+
+static inline void avl_set_right(struct avl_node *node, avl_t val)
+{
+	node->right = val;
+}
+
+static inline void avl_set_parent(struct avl_node *node, avl_t val)
+{
+	node->parent = val;
+}

Not too big ;)

Quoted 70 lines

net/core/alloc/avl.c new file +70 -0

+static inline void avl_rotate_complete(struct avl_node *parent, struct avl_node *node, int cpu)
+{
+	avl_set_parent(node, parent->parent);
+	if (parent->parent != AVL_NODE_EMPTY) {
+		if (parent->pos == AVL_RIGHT)
+			avl_set_right(avl_get_node(parent->parent, cpu), node->id);
+		else
+			avl_set_left(avl_get_node(parent->parent, cpu), node->id);
+	}
+	avl_set_parent(parent, node->id);
+}
+
+static inline void avl_ll(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *left = avl_get_node(node->left, cpu);
+	
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_left(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_LEFT;
+	if (!left) {
+		avl_set_right(parent, AVL_NODE_EMPTY);
+	} else {
+		avl_set_parent(left, parent->id);
+		left->pos = AVL_RIGHT;
+		avl_set_right(parent, left->id);
+	}
+}
+
+static inline void avl_rr(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+	struct avl_node *right = avl_get_node(node->right, cpu);
+
+	avl_rotate_complete(parent, node, cpu);
+	avl_set_right(node, parent->id);
+	node->pos = parent->pos;
+	parent->pos = AVL_RIGHT;
+	if (!right)
+		avl_set_left(parent, AVL_NODE_EMPTY);
+	else {
+		avl_set_parent(right, parent->id);
+		right->pos = AVL_LEFT;
+		avl_set_left(parent, right->id);
+	}
+}
+
+static inline void avl_rl_balance(struct avl_node *node, int cpu)
+{
+	avl_rr(node, cpu);
+	avl_ll(node, cpu);
+}
+
+static inline void avl_lr_balance(struct avl_node *node, int cpu)
+{
+	avl_ll(node, cpu);
+	avl_rr(node, cpu);
+}
+
+static inline void avl_balance_single(struct avl_node *node, struct avl_node *parent)
+{
+	node->balance = parent->balance = AVL_BALANCED;
+}
+
+static inline void avl_ll_balance(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+
+	avl_ll(node, cpu);

net/core/alloc/avl.c line 208

Quoted 10 lines

net/core/alloc/avl.c new file +10 -0

+	avl_balance_single(node, parent);
+}
+
+static inline void avl_rr_balance(struct avl_node *node, int cpu)
+{
+	struct avl_node *parent = avl_get_node(node->parent, cpu);
+
+	avl_rr(node, cpu);
+	avl_balance_single(node, parent);
+}

All way too big.

(Yes, avl_rr_balance() has a single callsite, as does avl_ll_balance(), but they each have separate copies of the very large avl_rr())

net/core/alloc/avl.c line 812

Quoted 3 lines

net/core/alloc/avl.c new file +3 -0

+	/*
+	 * NTA steals pages and never return them back to the system.
+	 */

That's the only code comment in this entire 882-line file?

?* full per CPU allocation and freeing (objects are never freed on ????????different CPU)

Am Monday 14 August 2006 13:04 schrieb Evgeniy Polyakov:

Quoted 2 lines

?* full per CPU allocation and freeing (objects are never freed on ????????different CPU)

Many of your data structures are per cpu, but your underlying allocations are all using regular kzalloc/__get_free_page/__get_free_pages functions. Shouldn't these be converted to calls to kmalloc_node and alloc_pages_node in order to get better locality on NUMA systems?

OTOH, we have recently experimented with doing the dev_alloc_skb calls with affinity to the NUMA node that holds the actual network adapter, and got significant improvements on the Cell blade server. That of course may be a conflicting goal since it would mean having per-cpu per-node page pools if any CPU is supposed to be able to allocate pages for use as DMA buffers on any node.

	Arnd <><

Quoted 9 lines · Arnd Bergmann

Am Monday 14 August 2006 13:04 schrieb Evgeniy Polyakov:

Quoted 2 lines

?* full per CPU allocation and freeing (objects are never freed on ????????different CPU)

Many of your data structures are per cpu, but your underlying allocations are all using regular kzalloc/__get_free_page/__get_free_pages functions. Shouldn't these be converted to calls to kmalloc_node and alloc_pages_node in order to get better locality on NUMA systems?

Quoted 6 lines

OTOH, we have recently experimented with doing the dev_alloc_skb calls with affinity to the NUMA node that holds the actual network adapter, and got significant improvements on the Cell blade server. That of course may be a conflicting goal since it would mean having per-cpu per-node page pools if any CPU is supposed to be able to allocate pages for use as DMA buffers on any node.

Doesn't alloc_pages() automatically switches to alloc_pages_node() or alloc_pages_current()?

Quoted 2 lines

Doesn't alloc_pages() automatically switches to alloc_pages_node() or alloc_pages_current()?

That's not what's wanted. If you have a slow interconnect you always want to allocate memory on the node the network device is attached to.

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

From: Evgeniy Polyakov <[email protected]>
Date: Wed, 16 Aug 2006 13:00:31 +0400

Quoted 3 lines

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

netdev_alloc_skb() knows the netdevice, and therefore you can obtain the "struct device;" referenced inside of the netdev, and therefore you can determine the node using the struct device.

Quoted 11 lines · David Miller

From: Evgeniy Polyakov <[email protected]>
Date: Wed, 16 Aug 2006 13:00:31 +0400

Quoted 3 lines

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

netdev_alloc_skb() knows the netdevice, and therefore you can obtain the "struct device;" referenced inside of the netdev, and therefore you can determine the node using the struct device.

It's not that easy unfortunately. I did what you describe above in my first prototype but then found out the hard way that the struct device in the netdevice can be a non-pci one, e.g. for pcmcia. Im that case the kernel will crash on you becuase you can only get the node infortmation for pci devices. My current patchkit adds an "int node" member to struct net_device instead. I can repost the patchkit ontop of -mm (which is the required slab memory leak tracking changes) if anyone cares.

Quoted 13 lines · Christoph Hellwig

Quoted 11 lines · David Miller

From: Evgeniy Polyakov <[email protected]>
Date: Wed, 16 Aug 2006 13:00:31 +0400

Quoted 3 lines

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

netdev_alloc_skb() knows the netdevice, and therefore you can obtain the "struct device;" referenced inside of the netdev, and therefore you can determine the node using the struct device.

Quoted 7 lines

It's not that easy unfortunately. I did what you describe above in my first prototype but then found out the hard way that the struct device in the netdevice can be a non-pci one, e.g. for pcmcia. Im that case the kernel will crash on you becuase you can only get the node infortmation for pci devices. My current patchkit adds an "int node" member to struct net_device instead. I can repost the patchkit ontop of -mm (which is the required slab memory leak tracking changes) if anyone cares.

Can we check device->bus_type or device->driver->bus against &pci_bus_type for that?

We could, but I'd rather waste 4 bytes in struct net_device than having such ugly warts in common code.

From: Christoph Hellwig <[email protected]>
Date: Wed, 16 Aug 2006 10:38:37 +0100

Quoted 2 lines

We could, but I'd rather waste 4 bytes in struct net_device than having such ugly warts in common code.

Why not instead have struct device store some default node value? The node decision will be sub-optimal on non-pci but it won't crash.

Quoted 5 lines · Christoph Hellwig

Quoted 2 lines

Doesn't alloc_pages() automatically switches to alloc_pages_node() or alloc_pages_current()?

That's not what's wanted. If you have a slow interconnect you always want to allocate memory on the node the network device is attached to.

There is drawback here - if data was allocated on CPU wheere NIC is "closer" and then processed on different CPU it will cost more than in case where buffer was allocated on CPU where it will be processed.

But from other point of view, most of the adapters preallocate set of skbs, and with msi-x help there will be a possibility to bind irq and processing to the CPU where data was origianlly allocated.

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

There is drawback here - if data was allocated on CPU wheere NIC is "closer" and then processed on different CPU it will cost more than in case where buffer was allocated on CPU where it will be processed.

But from other point of view, most of the adapters preallocate set of skbs, and with msi-x help there will be a possibility to bind irq and processing to the CPU where data was origianlly allocated.

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

Quoted 11 lines · Evgeniy Polyakov

There is drawback here - if data was allocated on CPU wheere NIC is "closer" and then processed on different CPU it will cost more than in case where buffer was allocated on CPU where it will be processed.

But from other point of view, most of the adapters preallocate set of skbs, and with msi-x help there will be a possibility to bind irq and processing to the CPU where data was origianlly allocated.

So I would like to know how to determine which node should be used for allocation. Changes of __get_user_pages() to alloc_pages_node() are trivial.

There are two separate memory areas here: Your own metadata used by the allocator and the memory used for skb data.

avl_node_array[cpu] and avl_container_array[cpu] are only designed to be accessed only by the local cpu, so these should be done like

avl_node_array[cpu] = kmalloc_node(AVL_NODE_PAGES * sizeof(void *),

			GFP_KERNEL, cpu_to_node(cpu));

or you could make the whole array DEFINE_PER_CPU(void *, which would waste some space in the kernel object file.

Now for the actual pages you get with __get_free_pages(), doing the same (alloc_pages_node), will help accessing your avl_container members, but may not be the best solution for getting the data next to the network adapter.

	Arnd <><

Quoted 17 lines · Evgeniy Polyakov

Quoted 15 lines · Arnd Bergmann

Am Monday 14 August 2006 13:04 schrieb Evgeniy Polyakov:

Quoted 2 lines

?* full per CPU allocation and freeing (objects are never freed on ????????different CPU)

Many of your data structures are per cpu, but your underlying allocations are all using regular kzalloc/__get_free_page/__get_free_pages functions. Shouldn't these be converted to calls to kmalloc_node and alloc_pages_node in order to get better locality on NUMA systems?

OTOH, we have recently experimented with doing the dev_alloc_skb calls with affinity to the NUMA node that holds the actual network adapter, and got significant improvements on the Cell blade server. That of course may be a conflicting goal since it would mean having per-cpu per-node page pools if any CPU is supposed to be able to allocate pages for use as DMA buffers on any node.

Quoted 2 lines

Doesn't alloc_pages() automatically switches to alloc_pages_node() or alloc_pages_current()?

That's not what's wanted. If you have a slow interconnect you always want to allocate memory on the node the network device is attached to.

That's not true on all NUMA systems (that they have a slow interconnect) I think on x86-64 I would prefer if it was distributed evenly or maybe even on the CPU who is finally going to process it.

-Andi "not all NUMA is an Altix"

Quoted 5 lines · Andi Kleen

That's not true on all NUMA systems (that they have a slow interconnect) I think on x86-64 I would prefer if it was distributed evenly or maybe even on the CPU who is finally going to process it.

-Andi "not all NUMA is an Altix"

The Altix NUMA interconnect has the same speed as far as I can recall as Hypertransport. It is the distance (real physical cable length) that creates latencies for huge systems. Sadly the Hypertransport is designed to stay on the motherboard. Hypertransport can only be said to be fast because its only used for tinzy winzy systems of a few processors. Are you saying that the design limitations of Hypertransport are an advantage?

So ideal would be something dynamic to turn on/off io placement, maybe based on node_distance() again, with the threshold tweakable per architecture?

Also I must say it's still not quite clear to me if it's better to place network packets on the node the device is connected to or on the node which contains the CPU who processes the packet data For RX this can be three different nodes in the worst case (CPU processing is often split on different CPUs between softirq and user context), for TX two. Do you have some experience that shows that a particular placement is better than the other?

IMHO the network memory allocator is being a little too focused on one problem, rather than looking at a general enhancement.

Have you looked into something like the talloc used by Samba (and others)?
http://talloc.samba.org/
http://samba.org/ftp/unpacked/samba4/source/lib/talloc/talloc_guide.txt

By having a context, we could do better resource tracking and also cleanup would be easier on removal.