How can I overwrite the first part of a struct in memory with a pointer?

Question

I have a memory address of the start of a number of structs, but need to eliminate some from my output. I think the memory space would look something like

+------------------+------------------+------------------+
|      struct      |     struct       |     struct       |
|  linux_dirent64{ |  linux_dirent64{ |  linux_dirent64{ |
|      first}      |     second}      |     third}       |
+------------------+------------------+------------------+
                    |*p|-------------->| |

As I'm iterating through each struct and returning some data in it, there may be one I need to skip. Would overwriting the first part of the struct with a pointer to the next give me the result I'm after? If so, how do I do that? And if not, how should I approach this?

I know there would be an easier solution if I modified the struct to include what I needed, but unfortunately it's not an option as it's part of the Linux Kernel.

Thanks for any replies.

EDIT: As everyone is interested, I'm filtering the structs based on filename. At the moment, I'm literally overwriting the d_name part with O's so it isn't returned by a system call. However this causes different problems depending on which application issues the system call so I need a more thorough way of getting rid of an instance of the struct.

I've since come up with the following, however it gets killed by the kernel if the d_name test returns true.

while(pos < length){
    printk("d_name = %s\t| pos = %i\t| d_reclen = %i\t| st = %i|\n", dirent->d_name, pos, dirent->d_reclen, st);
    if((st = strcmp(dirent->d_name, "testFile")) == 0){
        printk("Out of context file %s\n", dirent->d_name);
        posOverwrite = pos;
        size = dirent->d_reclen;
        while(posOverwrite < length){
            struct linux_dirent64 *next = (struct linux_dirent64 *)(pos + dirent->d_reclen);
            memcpy(dirent, next, sizeof(next));
            dirent = next;
            next = next + next->d_reclen;
        }
        dirent = (struct linux_dirent64 *) pos;
        continue;
    }
    pos = pos + dirent->d_reclen; //Push our position along according to the size of the dirent
    dirent = (struct linux_dirent64 *) (p+pos); //point our dirent to the next calculated system dirent
}

In the end I solved this by creating the new memory buffer, and copying all the structs I needed to the new buffer, leaving out any I didn't based on the d_name test. After I'd gone through the whole list, I then memcpy over my entire new list. Thanks for all the help guys :)

Answer 1

You're mixing things here -- you essentially have an array of fixed-size structs; you can't really turn that into a linked-list type structure in-place. To do what you want to do, each time you find one to remove, you will have to copy the rest of the list into the previous position.

Answer 2

What do you mean by "may be one I need to skip"? I'm assuming you have an array of structs, and there are some elements of this array you want to remove?

Arrays have to be contiguous. So, generally, there are two ways to do this - depending on how your code is structured one or the other may be easier.

1. Swap the element you want to eliminate with the first element in the array, then increment the pointer to the first element in the array, and decrement the count of elements in the array

2. Swap the element you want to eliminate with the last element in the array, then decrement the count of elements in the array

Of course, this is for appearances only. Don't let these pointer operations mess up your memory management.

Answer 3

What you describe doesn't make sense.

In which structs would you do the overwrite of the pointer? Must be something making them special - can't you use the same specialty for just skipping them in the loop?

struct linux_dirent {
    unsigned long   d_ino;
    unsigned long   d_off;
    unsigned short  d_reclen;
    char        d_name[1];
};

Are you skipping some d_ino? Which ones?

Answer 4

Here's some untested code modeled after remove_if from C++:

typedef struct linux_dirent64 dirent;

/* example predicate function - modify as needed */
/* returns nonzero if the file should be filtered out */
int has_foo_prefix(const dirent* ent)
{
  return !strncmp(ent->d_name, "foo", 3);
}

/* given a predicate, moves "good" entries to front, returns new end */
typedef int (*predicate)(const dirent*);
dirent* filter(dirent* array, dirent* end, predicate pred)
{
  for (dirent* slow = array, fast = array; fast < end; fast++) {
    if (!pred(*fast)) { /* keep this entry */
      if (fast != slow) { /* need to move this entry forward */
        memcpy(slow, fast, sizeof(dirent));
      }
      slow++;
    }
  }
  return slow;
}

/* example call */
dirent* array = ..., end = ...;
end = filter(array, end, has_foo_prefix);

The idea is that the unwanted elements of the array are overwritten step by step with the wanted ones, leaving only the wanted ones at the front of the array, which then effectively has a new (usually smaller) size. It's O(n) and does minimal allocation.

There is one important bug in my code which I'm leaving unaddressed for now: the variable length nature of the array elements. If a longer element needs to replace a shorter one, this is a problem. And in any case the code I wrote needs more pointer-twiddling to advance through the array correctly, but I'm leaving it as-is to be built upon. I'll note that as you advance through the array and skip some elements, you will see this problem less and less because of the extra space given by the "bad" elements. So the running time may not be worse than in the simplistic version unless the input is pathological.