Subj : Re: Block based virtual harddisk library
To   : comp.programming
From : Ed Prochak
Date : Mon Sep 19 2005 10:51 am


M.Barren@gmail.com wrote:
> Ed Prochak wrote:
>
> > This seems closely related to the virtual memory problem of operating
> > systems. Maybe you can get some ideas from searching that topic?
>
> Yes, I think you're right. I've read one paper on that so far, but I
> will continue to research in that area.
>
[I have no suggestions about the trie structure right now.

>
> > In fact this solves your free block problem. All you need in memory is
> > the location of the first free physical disc block. Since these blocks
> > are free, you can store freelist pointers in each one, chaining them
> > together. When the API frees a block, you insert it on the head of the
> > free list. When the API allocates a block, you return the current head
> > of the list and set the new head to the next one on the list. So you do
> > NOT need to keep the list of ALL free blocks in memory.
>
> Interesting. Thank you for mentioning it. Quite a basic technique which
> i'd completely forgotten about! However after a bit of more thought to
> it, I came up with this: Whenever a block is freed, we will move the
> last block in the container to fill its space. This method will
> definitly cause performace loss, but as I stated before, my main goal
> is to keep the container file as storage efficient as possible. Using
> this method, we won't have any free blocks to worry about. I'm 90% sure
> I'll go with this, but I'm still open for ideas in that 10%.

Well there is no trouble making a double linked list. Then adding to
the end is no harder than adding to the front. So I'd say the 10% went
down to about 2%.

Keep in touch.

.