MemoryAllocation SpinLock vs Interrupts

[alwaysnub]

When i first started my OS, i noticed a race condition when it came to my memory allocation function and interrupts.
My memory allocation function originally used a Spin Lock to keep multiple tasks from allocating memory at the same time (manipulating and corrupting data fields).
However, some of my interrupt routines used memory allocation to create a new separate task, and this is where the problem is.
If a task is in the process of allocating memory and is interrupted, and the interrupt tries to allocate memory, the interrupt will loop forever in the SpinLock waiting for a lock.
Because the task that has the lock is actually the same task.

To resolve this problem i created a solution. I call it the MctLock method (Must Complete Task Lock)
It simply disables interrupts and re-enables them when MctUnlock is called if they were previously enabled.
I also use this method for adding, removing and switching tasks.

Here is the code:

Code: Select all

NAKED DWORD API MctLock()
{
	__asm
	{
		pushfd;
		pop EAX;
		and EAX,0x200;
		shr EAX,9;
		CLI;
		ret;
	}
}

NAKED VOID API MctUnlock(DWORD LockValue)
{
	__asm
	{
		push EAX;
		mov EAX,[esp+8];
		cmp EAX,0;
		je DontEnableInterrupts;
		STI;
DontEnableInterrupts:
		pop EAX;
		ret 4;
	}
}

NOTE: The LockValue returned by MctLock must be stored local to the thread/task, if its global it will not have the effect as expected.

I'm worried however that this will cause slow performance, and that some interrupts might not fire at all or be missed since there disabled.
If anyone has seen this issue, how did you resolve this problem?
Any ideals or solutions to this kind of thing?

[Ready4Dis]

Oh yes, that's a fun problem . I am still trying to figure out the best way to keep my interrupt separate without locking. So far I came up with using a flag/list, where I can add things into a list to be processed instead of doing the same thing in both places. This was for my task switching (I can't read a task from the list in my interrupt while updating said task list in a process). So, I had to get creative with the book keeping. My task manager simply sets tasks as marked for deletion and my interrupt does the updating of the list itself to remove it. This way I can't have a partially removed tasks in the list and/or I don' t need a lock on my list (which could cause a race condition). I don't now if you could do something similar, but I do knows ome kernels just disable/mask interrupts (L4, i'm looking at you) to get around the problem.

Now, since you're talking about memory, if you disable interrupts, then a page fault happens... how does it get memory if another process has your memory manager locked out? What if they're both on the same CPU? Remember, a page fault is a non-maskable interrupt, so even if you disable interrupts, it's going to happen and you need to be prepared (aka, your physical memory manager can't be locked, nor your virtual).

[Techel]

You could just treat the interrupt routine like a normal piece of code, .i.e. dont disable interrupts.

[Ready4Dis]

You could just treat the interrupt routine like a normal piece of code, .i.e. dont disable interrupts.

That still doesn't fix the problem of a page not being present and an interrupt being generated... if the program relies on the functionality of the interrupt, you cannot just simply ignore the problem. If you can guarantee that a process the interrupt needs will NEVER need that interrupt, then yes you can do this. Unfortunately, this is hard to guarantee in most cases, especially when looking at apps that rely/wait on other apps/drivers. It's not impossible, but I'm sure there is a reason most kernel code is not re entrant to date.

[alwaysnub]

That still doesn't fix the problem of a page not being present and an interrupt being generated

Right.

@Roflo

I should have clarified that the interrupts I'm referring to are Not software generated, they are hardware generated (i.e, PIT, USB, Other).
This means they can happen any time while a function that uses a lock is executing (i.e my memory allocation function).

[Techel]

Oh ok.
I think hardware interrupts shouldn't call os-functions anyway but only notify the driver's main code that the interrupt has been received.

[alwaysnub]

I think hardware interrupts shouldn't call os-functions anyway but only notify the driver's main code that the interrupt has been received.

Ok, but what kind of notification are we talking about. My custom implementation of a message queue uses a FIFO method, to accomplish this it also uses a SpinLock .
I was thinking that in the case of USB interrupts, each interrupt had to be dealt with according to its specific status (Create a task passing interrupt status), but since the status in the register does not change until cleared, that may not be the case, i will have to think more about how it could be implemented correctly.

My task manager simply sets tasks as marked for deletion and my interrupt does the updating of the list itself to remove it.

I had the same ideal when i first ran into this problem, but what about Freeing task memory? don't you allocate any memory for your tasks? (Stack, Message Queue, etc)
If your Deallocate/Free memory functions don't use a lock, what kind of memory allocation method do you use?

I'm thinking that having the interrupt task switch update the list might hurt performance of other tasks since we want to switch as fast as possible when a timed interrupt switch is generated.
However, it probably wouldn't be enough to notice anyways.

[Techel]

I mean anything done in the interrupt handler should be done in the driver, eg. the driver (which may consist of various threads) waits until such interrupt has been received.

[Ready4Dis]

My task manager simply sets tasks as marked for deletion and my interrupt does the updating of the list itself to remove it.

I had the same ideal when i first ran into this problem, but what about Freeing task memory? don't you allocate any memory for your tasks? (Stack, Message Queue, etc)
If your Deallocate/Free memory functions don't use a lock, what kind of memory allocation method do you use?

I'm thinking that having the interrupt task switch update the list might hurt performance of other tasks since we want to switch as fast as possible when a timed interrupt switch is generated.
However, it probably wouldn't be enough to notice anyways.

Let me make sure you understand, it ONLY updates the pointers in the list, it does not generate a new item or delete the old item, simply moves it from one list to another via a couple of pointer changes. The service itself is responsible for allocating memory and freeing memory. I did this because I was worried about them both competing for a lock at the same time, so I made the running list lock free by only allowing one thing (interrupt) access to it. I could have solved this by setting a flag and then just letting the service check the flag each and every time, but that seemed like unnecessary overhead, why use an interrupt if you're just going to poll anyways? I'm still not 100% settled on the design, but so far it works ok.

[alwaysnub]

simply moves it from one list to another via a couple of pointer changes.

I did this because I was worried about them both competing for a lock at the same time, so I made the running list lock free by only allowing one thing (interrupt) access to it.

Ok, i understand, but (lol)... that doesn't explain your other list.
Only 1 thing can access your running list, which moves items to another list mark for deletion, but doesn't your other list need a lock since other things (tasks) can access it.

Perhaps im missing something.... XD

[Ready4Dis]

Ok, so for me right now, adding a task goes like this:
Call task manager, and add task .
Once the task if fully built, it puts it into a specific location (new task pointer) atomically so it can only be updated by a single instance ever. The interrupt checks this location when it fires to see if there is a new task that needs to run (and get added to the running list). I haven't finalized my deleting tasks yet, but it will most likely work similarly by building a dead list and then emptying it out one at a time in sync. I'm still working out specifics and trying to come up with a better method. I feel like there is a much better way, I just haven't found it yet . I was thinking about a way to atomically mark a thread as deleted from the list (updated the previous threads next pointer atomically) so when the interrupt is traversing, there is no way it could end up accessing the thread after I mark it for deletion. Worst case, it might skip a new thread since the next pointer wasn't updated yet...

[alwaysnub]

I was thinking about a way to atomically mark a thread as deleted from the list (updated the previous threads next pointer atomically) so when the interrupt is traversing, there is no way it could end up accessing the thread after I mark it for deletion.

Well, i think i found a good method using the (only the task switch interrupt can access the lists method).
However, I would like to point out some things:

Cons:
Slow, some reasons:

#1 If a user-mode app requests a list of tasks, the task switch interrupt will have to be the one that fills that list. (Assuming you/we implement such features)
This will no doubt make the task switch even slower.
#2 Because removing a task from the delete list is done using a flag and waiting for a task switch interrupt to actually remove it.

Pros:
Works, secure and tasks get deleted in order.

Great care will need to be taken to use this method and have it work correctly.
NOTE: I have NOT tested this code, its just an ideal for now.

Code: Select all

// Current Running Thread.
PTHREAD CurrentThread = 0;

// Thread Execute List.
PTHREAD FirstThread = 0;

// Thread Delete List.
PTHREAD ThreadsToDelete = 0;

// Add a thread to the delete list, and remove a thread from the delete list if it has been flag for it.
VOID AddToDeleteList(PTHREAD Thread)
{
	PTHREAD ThisThread;

	Thread->PrevThread = Thread->NextThread = 0;

StartOver:
	if (ThreadsToDelete == 0) ThreadsToDelete = Thread;
	else
	{
		if (ThreadsToDelete->Release == 2) // Remove thread from delete list?
		{
			ThisThread = ThreadsToDelete;
			ThreadsToDelete = ThreadsToDelete->NextThread;
			ThisThread->Release = 3; // Mark as removed after actually removing.
			goto StartOver;
		}

		// Get last entry.
		ThisThread = ThreadsToDelete;
		while (ThisThread->NextThread != 0)
		{
			ThisThread = ThisThread->NextThread;
		}

		ThisThread->NextThread = Thread; // Add to list.
	}
}

// Gets called after a timed (PIT) interrupt (task switch).
VOID RunNextThread()
{
	PTHREAD NextThread, ThisThread;

	NextThread = CurrentThread->NextThread;
	if (NextThread == 0) NextThread = FirstThread;

SkipThread:
	if (NextThread->Release == 1) // Remove thread from execute list?
	{
		// Remove from execute list.
		if (NextThread->PrevThread != 0) NextThread->PrevThread->NextThread = NextThread->NextThread;
		NextThread->NextThread->PrevThread = NextThread->PrevThread;
		// Mark for deletion.
		AddToDeleteList(NextThread);

		// Skip thread.
		NextThread = NextThread->NextThread;
		if (NextThread == 0) NextThread = FirstThread;
		goto SkipThread;
	}
	else if (ThreadsToDelete != 0) // We want to check if the delete list needs updating even if we aren't removing from the execute list.
	{
		if (ThreadsToDelete->Release == 2) // Remove thread from delete list?
		{
			ThisThread = ThreadsToDelete;
			ThreadsToDelete = ThreadsToDelete->NextThread;
			ThisThread->Release = 3; // Mark as removed after actually removing.
		}
	}

	CurrentThread = NextThread;
	JmpContext(&NextThread->Context);
}

// Called by main system message loop.
VOID FreeRemovedThreads()
{
	PTHREAD ThisThread;

	if (ThreadsToDelete != 0)
	{
		ThisThread = ThreadsToDelete;

		// We cant free ThisThread until it has been removed from the delete list, because the next pointer will no longer be valid after freeing.
		ThisThread->Release = 2; // Flag for removal from delete list.
		while (ThisThread->Release == 2); // Wait until removed. Release will be marked as 3 after it has been removed from the delete list.

		// Finally free resources.
		Free(ThisThread->Stack);
		Free(ThisThread);
	}
}

// Main task/system message loop.
VOID MainThread()
{
	while (TRUE)
	{
		// Do other stuff and whatever...
		//DispatchMessage

		// Free a thread if one needs it.
		FreeRemovedThreads();
	}
	// Shutdown computer or whatever.
}