Concatenating two memory buffers without memcpy.

Question

In C I have a function foo(char *) that accepts a memory pointer. in the caller, I have two different memory buffers, which I need to concatenate so I can pass one pointer foo(). Is there a way for me to do that without actually copying one buffer to the end of the other buffer and without changing foo() itself? I.e make the two buffers appear as one virtual continuous buffer to foo()

I need this for performance reasons. an O(n) solution (where n is one of the buffers length) is not acceptable for my case. Also, a Linux specific solution is fine, if it helps.

Thanks. Nir

Answer 1

Apologies for the shortness of the answer, but No, you can't.

As you've said yourself, you either need to

• Allocate one large buffer, and copy the seperate buffers to this or
• Change foo, to take multipe pointers.

Answer 2

No, there is no general solution for this.

Your only hope is if the two memory regions you want to concatenate already are directly after each other in the memory address space.

Answer 3

No, there is no such solution, unless you have knowledge about how memory allocator works, combined with pure luck.

Why do you allocate two buffers when you know that you'll need one afterwards? And how big are the buffers? Why are you avoiding copying? Have you measured that that would be a bottleneck?

Answer 4

Is it possible to modify foo() to take some sort of descriptor that describes a list of memory locations to act on (like a pointer to an array of structs with pointer/length pairs)?

That way there is no need for an O(N) copy operation.

If it's possible, that seems to be the only reasonable solution.

Answer 5

You could try adding another layer of indirection. It'd require you to rewrite foo to take an array of char *s, and to be able to handle the boundary condition between strings.

void foo(char **, int nstrings)
{ 
}

Then concatenating the strings is just a matter of creating a pointer array:

char *strings[2] = { string1, string2 };
foo (strings, 2);

Answer 6

Yes, there is a way.

Allocate memory for the buffers in a such way that they are adjacent in memory.

Example:

char* a = malloc(a_size + b_size);
char* b = a + a_size;

Answer 7

The following is a quite dirty solution, but maybe the only one in your case. And it will not work in all the cases (furthermore it is not predictable).

You can try to use mmap. When invoking mmap, you give it an address. mmap will try to allocate memory at the address you gave to it.

This solution is maybe the best you can have. You will only have to copy one char[], and none both.

You maybe would have to erase the \0 character at the end of the first.

And you can use the MAP_FIXED flag: if the mmap can not use the address, it will not allocate any memory space and return an error.

eg.

char a[20];
char b[20];

mmap(a + 20, 20, PROT_WRITE, MAP_FIXED, 0, 0);

Answer 8

This question seems to ask whether it is possible to concatenate the contents of two buffers (A and B) with the following constraints:

• You can't copy the contents of A or B.
• You can't change the address of A.
• The operation must have a worst case complexity < O(n).
• Presumably the address of B is such that A and B are not already concatenated. (As J.F. Sebastian pointed out in his answer, if you can allocate both A and B contiguously in the first place, you're done. But this seems like a degenerate case.)
• You must be able to do this from a Linux kernel driver (see comment under Jerome's answer).
• Neither A nor B is page aligned (see comment under original question).
• Neither A nor B is a multiple of the page size (see comment under original question).

Given all that, my answer is no: it is not possible.

Yes, an OS kernel can use the CPU's MMU (memory management unit, on architectures that have one) to remap memory in either the kernel virtual address space or the user virtual address space. Allocate a contiguous chunk of virtual address space, then remap A and B into that buffer by modifying the page table entries for the chunk of virtual address space to point to the physical addresses of A and B.

This doesn't change the virtual address of A per se (since the old virtual address is still valid), but it does require you to access it through a different virtual address. This may be a problem.

The granularity of this remapping on today's typical CPU architectures is based on the page size(s), and since A and B are not page aligned nor are they a multiple of the page size, you will not be able to make them completely line up. This is definitely a problem.

Remapping N bytes requires modifying at least one page table entry for every M bytes, where M is the page size. This means that the remapping operation has a computational complexity of O(n) anyway. Other operations such as allocating more physical pages for page tables, flushing caches and TLBs, etc. would have additional performance implications.

Also, I'm wondering if the goal of this question somehow involves DMA (direct memory access). When performing DMA with an archaic device that requires contiguous memory, no amount of remapping is going to help unless you have an IOMMU at your disposal. And a modern device that can do scatter-gather DMA wouldn't require contiguous buffers in the first place.