[SOLVED] Expand an array?

yaplej · 10-08-2009, 05:45 PM

I have an array that I declared in runtime. I need to expand it in runtime also.

I have a pointer called "sessions" that is initialized and points to a block of memory allocated by vmalloc_user. I have a second pointer to store the new memory location temporarily.

SESSIONSLOTS is the current size of the array.

I thought I would double the number of slots in the array, and then get a new block of memory, and save it in the temporary pointer. Then move the move the contents of the old array to the new one. Finally free the old memory, and update the original pointer to the new memory block.

I must be doing it wrong though because it just crashes the system.

Code:

SESSIONSLOTS = SESSIONSLOTS * 2;
tmp = vmalloc_user(SESSIONSLOTS * sizeof(struct session));  /* Initialize sessions array. */
memmove(tmp, sessions, (SESSIONSLOTS / 2));
vfree(sessions);
sessions = tmp;

jlinkels · 10-08-2009, 09:20 PM

I think you are using the sizeof in the wrong way. session is a pointer to some struct. sizeof(struct session) does not give you the size of the session structure.

You can only do sizeof if you use the type of the struct, e.g.

Code:

struct session {
  start integer;
  end integer;
};

then sizeof (session) is valid.

In case you did do this, then session is not a pointer, and you cannot use it in a function to move memory.

You should have something like:
struct session *sessionptr
and then you can make sessionptr point to the first session structure.

jlinkels

yaplej · 10-09-2009, 02:29 AM

session is just the structure defined earlier. sessions is a pointer to a block of memory assigned by vmalloc using the sizeof(session) * SESSIONSLOTS. This gets a block of memory able to hold a number (SESSIONSLOTS) worth of the structure session. I am sure that this is part is valid because initially creating the array works fine.

I think my problem is that this function accepts the sessions as a pointer. The pointer is a global variable in a LKM, but because its passed as a parameter in the function I think it becomes a local pointer in that function, and so when I reassign the pointer to a new block of memory it does not update the global pointer.

However vfree still frees the memory making the global sessions pointer dead/invalid.

graemef · 10-09-2009, 03:10 AM

where does it crash?
what is the data type of SESSIONSLOTS?
what is the value of SESSIONSLOTS when it crashes?

jlinkels · 10-09-2009, 06:06 AM

Quote:

Originally Posted by yaplej

session is just the structure defined earlier. sessions is a pointer to a block of memory assigned by vmalloc using the sizeof(session) * SESSIONSLOTS.

My fault, I overlooked the difference between session and sessions.

A good habit would be to check the value of tmp after vmalloc_user to make sure it is not null. No memory operation should be done without checking the return value of the pointer.

I don't see an easy explanation for the crash, the code looks sound. It might be time for a debugger session to see where exactly the crash happens.

jlinkels

yaplej · 10-09-2009, 04:37 PM

I am not sure if it crashes before or after it tries to expand the array. I was starting to think that the global sessions pointer isnt actually the one being updated, and this function frees the memory the global pointer is pointing to. So that could be the cause of the crash.

SESSIONSLOTS is just an integer value. I was setting it to 1 so it would require the array to be expanded after the first session is used. I can confirm that the first sessions works fine. Its when the second session tries to add itself into the array, and it needs expanded when it crashes.

yaplej · 10-09-2009, 05:45 PM

I rewrote this a little bit. I also put some extra error handling in, and its definatly the block that expands the array. If I comment it out the it does not crash.

Problem area.

Code:

SESSIONSLOTS = SESSIONSLOTS * 2;
	tmp = sessions;
	sessions = vmalloc_user(SESSIONSLOTS * sizeof(struct session));  /* Initialize sessions array. */
	memmove(sessions, tmp, (SESSIONSLOTS / 2))* sizeof(struct session));
	vfree(tmp);
	goto insertsession;

Code:

/* Structure used to store TCP session info. */
struct session {
	__u32 largerIP; /* Stores the larger IP address. */
	__u16 largerIPPort; /* Stores the larger IP port #. */
	__u32 smallerIP; /* Stores the smaller IP address. */
	__u16 smallerIPPort; /* Stores the smaller IP port #. */
	__u32 local; /* Stores the local PacketProcessor IP. */
	__u32 remote; /* Stores the remote PacketProcessor IP. */
	__u8 state; /* Stores the TCP session state. */
};


/* 
 * Inserts a new session into the sessions array.
 * Will also handle expanding the array later.
 */
static __s64
insertsession(__u32 largerIP, __u16 largerIPPort, __u32 smallerIP, __u16 smallerIPPort)
{
	struct session *tmp;
	__u32 i;
	
	insertsession:
	for (i = 0; i < SESSIONSLOTS; i++) {

		if (sessions[i].largerIP == 0) {

			sessions[i].largerIP = largerIP;
			sessions[i].largerIPPort = largerIPPort;
			sessions[i].smallerIP = smallerIP;
			sessions[i].smallerIPPort = smallerIPPort;
			return i;
		}	

	}
	
	/* 
	 * Session array was full.
	 * It should be expanded.
	 */
	printk(KERN_ALERT "INFO: Sessions array to small must expand it.\n");
	printk(KERN_ALERT "INFO: Session array size is %lu.\n",
					(long unsigned int)SESSIONSLOTS);
	SESSIONSLOTS = SESSIONSLOTS * 2;
	tmp = sessions;
	sessions = vmalloc_user(SESSIONSLOTS * sizeof(struct session));  /* Initialize sessions array. */
	memmove(sessions, tmp, (SESSIONSLOTS / 2)); //* sizeof(struct session));
	vfree(tmp);
	goto insertsession;
	return -1;
}

yaplej · 10-09-2009, 06:28 PM

I narrowed it down that its crashing when trying to allocate a new block of memory. I dont know why it works in one spot, but not in another.

graemef · 10-10-2009, 02:19 AM

You have a goto in your function which refers to the insertsession label which is at an earlier place in the function. Doesn't that therefore mean that you have a loop continually allocating more memory?

This can be coded without the goto and I would say that in almost all cases goto's are bad practice.

yaplej · 10-11-2009, 01:04 PM

The only reason the code to expand the array would run is if the array is out of slots, and i is not returned in the function. So once the array is expanded it tries to insert the session into the array again. Now that it has been expanded it should not loop, but return i, and end the function.

jlinkels · 10-11-2009, 01:35 PM

If largerIP happens to be 0, slots are inserted until the number of slots is used up. Then the memory is expanded, your slots are moved, and you start inserting again at the memory base address, starting at session 0. Why do you move anyway?

Secondly, and I said that before NEVER USE AN ALLOCATED MEMORY POINTER UNLESS YOU CHECKED IT IS NOT ZERO.

Furthermore, we only see the code, we are not computers and are apt to make errors in interpreting the code, and we don't know the contents of all variables and memory, no matter how much we want to help you. Please load the code in gdb, walk thru it once and you might find the error in 30 minutes.

Debugging by newsgroups is not the best idea with this low-level code.

jlinkels

yaplej · 10-11-2009, 02:23 PM

Well I am sure that largerIP will never be "0". largerIP represents the 32-bit binary of an IP address. IP 0.0.0.0 would never be routed so this it would never be seen by the kernel module. If somehow it were it would be seen as an "unused" slot, and another non-zero session would write over it.

I could not find any function to "expand" an array in a kernel module that works with vmalloc so I have to vmalloc an entire new array, and move the contents of the old array into the new one. Once thats done I can free the old array.

Ok so I should be checking my pointers before using them. Is not ZERO, or NULL? Is there a difference?

I dont think that gdb works on a kernel module.

jlinkels · 10-11-2009, 08:17 PM

Quote:

Originally Posted by yaplej

I could not find any function to "expand" an array in a kernel module that works with vmalloc so I have to vmalloc an entire new array, and move the contents of the old array into the new one. Once thats done I can free the old array.

As such there is nothing wrong with the way you expand the array and move the memory to the newly allocated block. I don't understand either why your code doesn't work.

Quote:

Originally Posted by yaplej

I dont think that gdb works on a kernel module.

You are writing a kernel module and you are not checking for a null pointer returned by a memory allocation function? Are you serious?
I am not sure whether GDB can debug kernel modules, but it is worth checking. Anyway, this piece of code you can run easily in user space feeding it with test vectors you generate yourself. A test vector is a struct of type session which you created yourself.
It is good programing practice to use NULL for a pointer check. It is defined in stdio.h. It is the same as 0x0.

jlinkels

sundialsvcs · 10-12-2009, 08:25 AM

Why does it have to be an array? Why not use a hash-table or some other existing container-class, which will take care of such messy details for you?

"Do not do a thing already done ..."

Let me elaborate a bit. There are many situations in the computer world where you find that you need to store some bit of data according to some "index." A classical 'array' is just fine if you know just how large the array needs to be, and the only index that you need is "consecutive integers," and if you plan to fill 'er up.

But if that's too restrictive, there's a whole slew of available data-structures ... already built for you in almost every language other than straight-C ... which are available for the purpose of "storing things." They're called by various names such as "hash" or "collection." The messy issues that you are facing right now become a non-issue, and you don't pay a performance-hit.

yaplej · 11-01-2009, 12:55 AM

I found that vmalloc() allocates memory using a method that is able to sleep. This does not work in an interupt context that my function is running in. Thus my problem. I was able to use a linked list to save my data rather than an array.