Memory Management With Linked List(s)

[chris]

If I'm implementing one linked list, would I need anything more than something like this?:

Code: Select all

struct list {
    int used;         /* Used or not */

    addr_t addr;    /* Address (start) */
    int len;           /* Length */

    struct list *next;
    struct list *prev;
};

What I'm still not too sure about is the relation between memory and each segment in the linked list. It can't be 1 segment: 1 page ???. In Tanenbaum's book his segments are either processes or "holes". I don't have processes yet, so how do I use the linked list? And do I set it up by just pointing the head to the address right after my pdir?

I can't seem to find any tutorials or source examples :-\

[Tim]

An item in a doubly-linked list just needs previous and next item pointers. (A singly-linked list just needs either a previous or a next pointer, although that means you can only look at items in a singly-linked list in one direction.)

So an item in a linked list might look like this:

Code: Select all

struct process_t
{
    process_t *prev, *next;
    // other process fields here
};

To maintain the list, you need to know where it begins and ends:

Code: Select all

process_t *proc_first, *proc_last;

You can enumerate all the items in a list:

Code: Select all

process_t *proc;
for (proc = proc_first; proc != proc_last; proc = proc->next)
    do_something(proc);

Where does the memory for each item come from? Well, usually from malloc. But I guess you're asking this because you're looking at implementing your physical memory manager using linked lists, so in this case, you'll have to be more inventive in finding memory for the items.

[chris]

@Tim; I read your MM tutorials again, and I understand things quite a bit better now .

At the moment, the only problem is if a linked list(s) would go well with my physical memory allocator, to manage which physical pages are used and not used. Also, if I use a linked list, how I would set it up without malloc or something.

Anybody know the answers?

@Tim; Btw, are you going to write the other tutorials that are mentioned in the MM ones. The MM ones are very useful:).

[BI lazy]

Chris, first, you need to code a kind of malloc library for your kernel: it manages a memory region YOU and only YOU set aside specially for this purpose: this malloc splits the memory in small regions. If you request a chunk of memory, malloc takes a chunk of the size header size+requested length (this is my way to do it), fills in the header fields, adjusts some control fields and returns the adress of the datafields beginning. Free just searches the chain of allocated memory and puts the piece in question into the free chunks list.

Second: YOU and only YOU calculate how many pages you have available in your system. you fill in the list of free physical memory like the following: set an integer to zero; then enter a while or a for loop and do while incrementing the integer by 4096 until it has reached the highest available adress: assign a list item; fill in the required fields (hint: look at the integer you increment); add the item to the list.

HtH

[Tim]

At the moment, the only problem is if a linked list(s) would go well with my physical memory allocator, to manage which physical pages are used and not used. Also, if I use a linked list, how I would set it up without malloc or something.

I can give you an answer when I've worked out the best way to do this myself .

OK, normally allocating items for a linked list is easy -- just use malloc. We'll ignore that for now as you don't have malloc available at this point in initialisation.

What I've been doing is setting aside a block of memory to contain all the list items in the page list, one per page. Then, when you want the page at address A, you get the item at mem_pages + (A / PAGE_SIZE). The problem is where to put this block. At the moment it goes after the end of the last multiboot module. I'm currently hitting a problem where, if you have lots of memory installed, or you have lots of modules loaded, the pages block goes across a 4MB boundary. The paging setup code at the start is pretty simple, because there's no way of dynamically allocating page tables, so at the moment I've decided to map 8MB at startup and hope that's enough.

@Tim; Btw, are you going to write the other tutorials that are mentioned in the MM ones. The MM ones are very useful:).

Maybe, but not any time soon...

[chris]

Hmm... interesting. I guess I'll have to go with the bitmap approach for now (unless someone is willing to explain the stack one), and used linked lists at the virtual memory manager level.

Maybe a temporary bitmap or stack could be set up until the OS intialization is at a stage where you can use malloc. Then replace the temporary bitmap with a linked list, and fill the linked list with the entries already in the bitmap?

[Tim]

The basic linked list approach isn't hard to do. It's just that the way I've done it requires a bit of though to avoid having an upper limit on the amount of physical memory the kernel can use.

[chris]

Would you be able to explain how to do it in a basic form (like how to set it up, etc)? I know for it a bitmap it's easy.. just make a variable for the bitmap and point it to the proper location.

Also, for the linked list, is it one item/node/segment per page? For example:

Code: Select all

struct list {
    int used;

    struct list *next;
    struct list *prev;
}

1 for every page frame allocated. If so, wouldn't this lead to a very long linked list; and would it have the performance issues as bitmap approach (without a superpage bitmap)?

[Tim]

You've got the right idea for the struct definition. The performance for a linked list is the same as for a stack. To allocate a page, you remove the topmost item. To free a page, you add an item to the top. Allocation from a bitmap is O(N), where N=amount of physical memory; allocation from a stack or linked list is O(1).

[chris]

Thanks.