OSDev.org

Posted: **Thu Nov 09, 2006 8:59 am**

Hi all, it has been a long time since I stopped dev-ing, but now I'm dev-ing again

I'm implementing a user system, group system etc. For this I need to give every user/group an id within the system. Every id can be referenced against a linked list which holds the data belonging to the id. This list is sorted and I'll use a binary search to find the data referenced by the id. Now I come to the problem of allocating id's. I can do this by just simply create a bitmap in memory and put id numbers in it, this is fine, but I want something more robust. Something like a stack or something?? Also in linux I noticed they use a hash table to allocate uid's, gid's and pid's etc. In my system all id's can be dynamic. What do you think is the best approach??

Posted: **Thu Nov 09, 2006 10:05 am**

Hi,

matthias wrote:What do you think is the best approach??

Is there any benefit (for security) in using a random number generator, so that it's difficult to predict which UID, GID or PID will be allocated next?

If the answer is "no", then what's wrong with something simple, like:

Code: Select all

   do {
      UID = ++lastUID;
   } while ( checkUID( UID ) != USED );

If ID's are 32-bit, then this saves you from having a huge bitmap, and it won't loop unless more than 4 billion UID's have been created (and possibly freed).

Cheers,

Brendan

Posted: **Thu Nov 09, 2006 10:16 am**

The answer is no on the security stuff. But what kinda lacks in your design is the way to chek if an id is used or not. I would still have to use a stack or bitmap to say wether an id is free. This would mean I'll have to do a search operation within the stack or reference the id to the bit in the bitmap en chek if it is set. So this leaves me with the idea of needing a bitmap right?

Posted: **Thu Nov 09, 2006 10:58 am**

Hi,

matthias wrote:The answer is no on the security stuff. But what kinda lacks in your design is the way to chek if an id is used or not. I would still have to use a stack or bitmap to say wether an id is free. This would mean I'll have to do a search operation within the stack or reference the id to the bit in the bitmap en chek if it is set. So this leaves me with the idea of needing a bitmap right?

I assumed you'd use the linked list and binary search for this:

matthias wrote:Every id can be referenced against a linked list which holds the data belonging to the id. This list is sorted and I'll use a binary search to find the data referenced by the id.

Of course this creates a new problem - balancing the binary tree. For e.g. if you add 1, then 2, then 3, then all of the additions would be on one side of the binary tree (effectively turning it into a linear search).

A relatively easy way to avoid this is to reverse the bits, so that bit 0 is swapped with bit 31, bit 1 is swapped with bit 30, bit 2 is swapped with bit 30, etc (e.g. "abcdefgh" in binary becomes "hgfedcba").

The end result of this would be a progression like 0x8000000, 0x4000000, 0xC000000, 0x2000000, 0xA000000, 0x6000000, ..., etc (for input values 1, 2, 3, 4, 5, 6). If the first number is 0x80000000 (i.e. if the first input value is 1) this leads to a pefectly balanced binary tree.

Cheers,

Brendan

Posted: **Thu Nov 09, 2006 11:22 am**

I think you missed my intentions

My goal:

- an id allocating system

Let me redefine my request:

I want a system which allocates id's, just integer values. Should I use bitmaps or a stack, or some other aproach??

For now I think the bitmap approach works best.

So this has nothing to do with my linked lists I have for holding user data. I just want to create id's which I can refer to an element in the list while creatin g the element

brendan wrote: Of course this creates a new problem - balancing the binary tree. For e.g. if you add 1, then 2, then 3, then all of the additions would be on one side of the binary tree (effectively turning it into a linear search).

A relatively easy way to avoid this is to reverse the bits, so that bit 0 is swapped with bit 31, bit 1 is swapped with bit 30, bit 2 is swapped with bit 30, etc (e.g. "abcdefgh" in binary becomes "hgfedcba").

The end result of this would be a progression like 0x8000000, 0x4000000, 0xC000000, 0x2000000, 0xA000000, 0x6000000, ..., etc (for input values 1, 2, 3, 4, 5, 6). If the first number is 0x80000000 (i.e. if the first input value is 1) this leads to a pefectly balanced binary tree.

When I add an element in the list I will sort it directly so that this problem does not occur

Posted: **Thu Nov 09, 2006 1:56 pm**

In one of the first "Game Programming Gems"-Books Scott Bilas wrote an article about an handle based resource manager. I assume this is exactly what you need.

You should google for "Generic based Handle Manager" or something along this line. It's a really straight-forward approach and therefore it was designed for realtime computer games, it was implemented with high performance in mind.

Hope this helps.

Posted: **Thu Nov 09, 2006 4:10 pm**

I looked it up, but is not compatible with the thing I want

It is interresting though

Posted: **Thu Nov 09, 2006 4:54 pm**

I use address of an object (process, thread) and use some strange math to get the ID.

Posted: **Fri Nov 10, 2006 5:35 am**

kataklinger wrote:I use address of an object (process, thread) and use some strange math to get the ID.

Sounds doable, but what about security? I can imagine referencing an id to the memory location of an object is not safe??

Posted: **Fri Nov 10, 2006 7:20 am**

Hmm... i can't imagine why. Any hint?

Posted: **Fri Nov 10, 2006 8:17 am**

By referencing an id to memory you know the physical address of an id, if for instance there is a leak in my OS someone could easily do more damage if he had acces to this memory. Also what if memory is shared by two id's?? Freeing one id will result in data-inconsistencies, which you don't want of course.

Posted: **Fri Nov 10, 2006 9:27 am**

matthias wrote:By referencing an id to memory you know the physical address of an id, if for instance there is a leak in my OS someone could easily do more damage if he had acces to this memory. Also what if memory is shared by two id's?? Freeing one id will result in data-inconsistencies, which you don't want of course.

There are such things as 'one-way functions' in mathematics. A reasonably strong hash function should mean that you can convert addresses to a reasonably unique ID (dependant on the algorithm you choose - just bear in mind that even a 'weak' hash function will probably only produce a collision 1 in every couple billion attempts or something of that order - pretty unlikely).

That, however, does not deal with the shared memory thing. There are a few ways of dealing with this, even if you do go with the address->ID idea. You could simply release the handle, leaving other handles to point to the memory and only free the memory when the last handle is released; or you could copy the data to somewhere else, free the memory and then update the remaining handles (I can't see why that would make sense compared to the first though). But I'm sure there are better ways of doing this than I've said.

Posted: **Fri Nov 10, 2006 12:08 pm**

matthias wrote:By referencing an id to memory you know the physical address of an id, if for instance there is a leak in my OS someone could easily do more damage if he had acces to this memory.

No you know virtual address, but still to access the process'/thread's/what so ever's information you must be in kernel mode and then you can simply call get_an_object_by_its_id().

matthias wrote:Also what if memory is shared by two id's?? Freeing one id will result in data-inconsistencies, which you don't want of course.

What's memory sharing got to do with allocation of ID's?

OSDev.org

ID system

ID system

Re: ID system