Skip to contentSkip to conversation

Sharing memory between kernelspace and userspace

DISCUSSION Jonathan Day 2 participants 3 messages Sep 14, 2006

lore
Share & tools
lore
#0 lore raw

Hi,

I'll start with a summary of the problems I need solved, and then get on with the explanation of why I need them solved.

1. I need a kernel driver to be able to allocate and deallocate, on a totally dynamic basis, userspace memory that is reachable by multiple applications.

2. I need a Really Efficient Method(tm) of knowing if a specified application (maybe thread) dies. Efficient here primarily means not tampering with anything outside the driver if at all humanly possible.

3. I would truly value some suggestions on which of the many ways of communicating with the kernel would offer the best way to handle a truly horrible number of very simple signals. Speed, here, is an absolute must. According to my boss, residual sanity on my part is not.

Ok, now for an overview of what I'm trying to do:

I'm having what is probably the world's second-dumbest problem. What I want to do is have a driver in kernelspace be able to allocate multiple chunks of memory that can be shared with userspace without having to do copies. So far, that doesn't sound like any big deal - the Linux Device Drivers book covers essentially this task.

There are several problems, however, that make this nasty. First, since the time before the kernel driver or user application can start (and therefore finish) processing a block of data is non-deterministic and there is a requirement the mechanism be as close to non-blocking as possible, so I need to be able to create and destroy chunks entirely on-the-fly with the least risk of either the driver or the application ending up with unexpectedly invalid pointers.

The second problem is that the interface between kernelspace and userspace is handling messages rather than packets, so I've absolutely no idea in advance how big a chunk is going to be. That is only known just prior to the data being put in the chunk allocated for it. Messages can be big (the specs require the ability to send a message up to 2Gb in size) which - if I'm reading the docs correctly - means I can't create the chunks in kernelspace.

Having an application create a userspace buffer and hand that off to the kernel is, again, documented. No problem there. It's the reverse direction that is the bugbear. I have to have the kernel driver ALSO create a userspace buffer and it's not clear to me how to do this.

Now we get to the fun part. The specs also require the driver be able to deliver to multiple applications. With zerocopy, this isn't a big deal as far as processing is concerned - there's no extra overhead no matter how many applications want to access the data.

The problem is that when any given application performs the read is, again, non-deterministic, and although the number of recipients is known in advance, the number of recipients for any given chunk is not. This means that the order in which chunks are deleted is going to be essentially random. It also means I need to watch the process table, 'cos I can't leave blocks permanently allocated if one or more recipients dies before signalling that it has finished with it.

The signals, overall, are all very simple. An application joins or leaves a group interested in a specific sequence of messages. An application finishes reading a named chunk or finishes writing one. An outbound sequence may be created or destroyed. An inbound sequence may be terminated. The device is either ready or it isn't.

There is, however, the interesting problem that some of these signals (such as inbound sequences terminating) that must be delivered to multiple applications. I'm assuming this is going to have to be done one application at a time, but if I can send such signals to the whole lot at once, I would prefer it.

Suggestions and brain transplants welcome.

Jonathan Day

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

#1 lore raw
Quoted 3 lines · Jonathan Day

1. I need a kernel driver to be able to allocate and deallocate, on a totally dynamic basis, userspace memory that is reachable by multiple applications.

Is there no possible way you can do the memory allocation fully in userspace? Let userspace allocate shared memory visible to multiple processes, and pass that into the kernel for it to write to.

If this is as high-speed as you imply, then you *really* don't want to be doing this on the fly (let alone from inside the kernel). All the high-bandwidth stuff I've worked on preallocated its buffers, as later on in the processing there are no hard guarantees as to either how much memory one can acquire *or* how long it will take to do so. Either one of those is a deal-breaker when dealing with fast data rates.

Quoted 6 lines

3. I would truly value some suggestions on which of the many ways of communicating with the kernel would offer the best way to handle a truly horrible number of very simple signals. Speed, here, is an absolute must. According to my boss, residual sanity on my part is not.

Just send a message down an fd? The wakeup/context-switch is the expensive part of that, I think, at least when dealing with only a few dozen fds. Or change it to be level- rather than edge-triggered, to coalesce the horrific number of events getting crammed down the processing side.

It sounds like this is the cheapest part of the process, so not worth the effort of optimizing it as much as finding better ways to do the rest of it.

Quoted 5 lines

I'm having what is probably the world's second-dumbest problem. What I want to do is have a driver in kernelspace be able to allocate multiple chunks of memory that can be shared with userspace without having to do copies.

Have userspace ask the driver if anyone has allocated it yet, if not, userspace allocates it and hands the pointer to it back to the driver so that it can hand it back out to the other calling processes who also want to subscribe to that data stream.

If another userspace process races with the first trying to ask if a buffer is available (first asked already, but hasn't yet given the driver the info), then the driver puts the second process to sleep until it's ready to hand back the buffer.

Quoted 9 lines

There are several problems, however, that make this nasty. First, since the time before the kernel driver or user application can start (and therefore finish) processing a block of data is non-deterministic and there is a requirement the mechanism be as close to non-blocking as possible, so I need to be able to create and destroy chunks entirely on-the-fly with the least risk of either the driver or the application ending up with unexpectedly invalid pointers.

Creating chunks on the fly is, I think, an operation that can take an arbitrary amount of time. If you *really* want to do that, you should instead just allocate as much as possible in the first place, and then you do your own memory management on blocks inside of that, never invoking the kernel's memory services after the initial allocation.

Quoted 9 lines

The second problem is that the interface between kernelspace and userspace is handling messages rather than packets, so I've absolutely no idea in advance how big a chunk is going to be. That is only known just prior to the data being put in the chunk allocated for it. Messages can be big (the specs require the ability to send a message up to 2Gb in size) which - if I'm reading the docs correctly - means I can't create the chunks in kernelspace.

Surely this is just an issue of writing the chunk to free memory? Either you have the memory available or you don't. If you do, no problem. If you don't, then you're screwed regardless, as allocating on the fly is not guaranteed to help you out.

Good luck,

Ray

#2 lore raw

Thanks for some absolutely wonderful suggestions.

Quoted 6 lines · --- Ray Lee
Quoted 1 line · Jonathan Day

1. I need a kernel driver to be able to allocate

and

Quoted 2 lines

deallocate, on a totally dynamic basis, userspace memory that is reachable by multiple applications.

Quoted 6 lines

Is there no possible way you can do the memory allocation fully in
userspace? Let userspace allocate shared memory visible to multiple
processes, and pass that into the kernel for it to write to.

I guess I could - I'd need a userspace program that was guaranteed to be running to handle the memory management, but that's really no different than any of the other daemons.

Quoted 5 lines

If this is as high-speed as you imply, then you *really* don't want to
be doing this on the fly (let alone from inside the kernel). All the
high-bandwidth stuff I've worked on preallocated its

Quoted 8 lines

buffers, as later
on in the processing there are no hard guarantees as to either how
much memory one can acquire *or* how long it will take to do so.
Either one of those is a deal-breaker when dealing with fast data
rates.

You are absolutely right and preallocation is definitely best. The problem lies in not knowing how much to pre-allocate, which either means using discontiguous chunks of memory or lots of copying - neither of which is good.

One hack-around I played with was to go right ahead and pre-allocate reasonable fixed-sized buffers, which would be physically discontiguous, and then massage the virtual memory tables so that anything outside of the kernel would see a single, continuous block. (Massaging an index is much faster than manipulating data.) As far as I can tell, though, the VMM is simply not designed for Evil Geeks to go re-organizing the virtual layout in any kind of sane way.

An alternative would be to have a generic pre-allocated dumping zone, where anything larger than the zone would get space allocated on-the-fly, but where initial data would be dumped as normal (giving the kernel time to do the allocation) and copied into the start of the final buffer in the CPU's spare time.

Beyond that, I'm stumped for ideas.

Quoted 12 lines
Quoted 1 line

3. I would truly value some suggestions on which

of

Quoted 1 line

the many ways of communicating with the kernel

would

Quoted 1 line

offer the best way to handle a truly horrible

number

Quoted 1 line

of very simple signals. Speed, here, is an

absolute

Quoted 1 line

must. According to my boss, residual sanity on my

part

Quoted 1 line

is not.

Quoted 9 lines

Just send a message down an fd? The
wakeup/context-switch is the
expensive part of that, I think, at least when
dealing with only a few
dozen fds. Or change it to be level- rather than
edge-triggered, to
coalesce the horrific number of events getting
crammed down the
processing side.

Good ideas.

Quoted 5 lines

It sounds like this is the cheapest part of the
process, so not worth
the effort of optimizing it as much as finding
better ways to do the
rest of it.

I would concur completely with that.

Quoted 7 lines
Quoted 1 line

I'm having what is probably the world's

second-dumbest

Quoted 4 lines

problem. What I want to do is have a driver in kernelspace be able to allocate multiple chunks of memory that can be shared with userspace without having to do copies.

Quoted 7 lines

Have userspace ask the driver if anyone has allocated it yet, if not,
userspace allocates it and hands the pointer to it back to the driver
so that it can hand it back out to the other calling processes who
also want to subscribe to that data stream.

As good as done. That's going to be relatively easy to implement.

Quoted 7 lines

If another userspace process races with the first trying to ask if a
buffer is available (first asked already, but hasn't yet given the
driver the info), then the driver puts the second process to sleep
until it's ready to hand back the buffer.

Ok. That should be doable. All requestees would need to be slept, as the time to malloc is unknown. The driver, on getting the data back, would need to finish any sleepifying it was doing before jumping to the
unsleep & deliver.

Quoted 16 lines
Quoted 1 line

There are several problems, however, that make

this

Quoted 1 line

nasty. First, since the time before the kernel

driver

Quoted 1 line

or user application can start (and therefore

finish)

Quoted 1 line

processing a block of data is non-deterministic

and

Quoted 1 line

there is a requirement the mechanism be as close

to

Quoted 2 lines

non-blocking as possible, so I need to be able to create and destroy chunks entirely on-the-fly with

the

Quoted 2 lines

least risk of either the driver or the application ending up with unexpectedly invalid pointers.

Quoted 10 lines

Creating chunks on the fly is, I think, an operation that can take an
arbitrary amount of time. If you *really* want to do that, you should
instead just allocate as much as possible in the first place, and then
you do your own memory management on blocks inside of that, never
invoking the kernel's memory services after the initial allocation.

You covered a few possibilities earlier and I've added a few to the list, so I think we can eliminate the kernel memory allocation. Which is a BIG relief.

Quoted 12 lines
Quoted 2 lines

The second problem is that the interface between kernelspace and userspace is handling messages

rather

Quoted 1 line

than packets, so I've absolutely no idea in

advance

Quoted 6 lines

how big a chunk is going to be. That is only known just prior to the data being put in the chunk allocated for it. Messages can be big (the specs require the ability to send a message up to 2Gb in size) which - if I'm reading the docs correctly - means I can't create the chunks in kernelspace.

Quoted 7 lines

Surely this is just an issue of writing the chunk to free memory?
Either you have the memory available or you don't. If you do, no
problem. If you don't, then you're screwed regardless, as allocating
on the fly is not guaranteed to help you out.

It's all down to how fast free memory can be reserved, how to avoid blocking small messages when a large message is inbound but takes excessive time to deliver, and how to minimise memory fragmentation.

There are going to be options which - to someone less experienced in the heavy fine-tuning like myself - would seem inefficient but which (in practice) provide overall much better performance than alternatives. Further, in a parallel architecture, what is efficient at one scale may or may not be at another.

Thanks for your help - it is greatly appreciated - and please feel free to forward any other thoughts you might have.

Jonathan Day

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com