cbitmapoperating-systemfilesystems

Free space bitmap C implementation


I trying to develop a simple file system (Linux kernel) and I'm thinking of using bitmap to keep track of used/free blocks as described in here:

https://en.wikipedia.org/wiki/Free_space_bitmap

However, I could not find any implementation of such system in C. I would like to see some examples so I could implement a similar thing to my system.

Any suggestion where I could find them?


Solution

  • Here's a quick implementation I made after reading this question.

    int mem_block_size;
    int mem_block_count;
    uint *bit_map;
    char *buffer;
    
    void init_memory_map(int block_size, int block_count)
    {
        mem_block_size = block_size;
        mem_block_count = block_count;
        buffer = (char*)malloc(block_size * block_count);
        bit_map = (uint*)calloc((block_count / 32) + ((block_count % 32) != 0), 4);
    }
    
    inline
    int is_allocated(int index)
    {
        return (bit_map[index / 32] & (1 << (index % 32))) != 0;
    }
    
    inline
    void allocate_frame(int index)
    {
        bit_map[index / 32] |= 1 << (index % 32);
    }
    
    inline
    void clear_frame(int index)
    {
        bit_map[index / 32] &= ~(1 << (index % 32));
    }
    
    char* allocate_block(int block_count)
    {
        int index = 0, free_frames = 0;
        while(index < mem_block_count)
        {
            if (!is_allocated(index))
            {
                free_frames++;
                if (free_frames == block_count)
                {
                    int frame_index = index - block_count + 1;
    
                    index = 0;
                    while(index < block_count)
                    {
                        allocate_frame(frame_index + index);
                        index++;
                    }
                    return (buffer + frame_index * mem_block_size);
                }
            }
            else free_frames = 0;
            index++;
        }
    
        perror("memory error\n");
        return 0;
    }
    

    The basic idea is, you maintain a bit map which keep tracks of allocated frames. each frame act's as a buffer of fixed size. when you are done with the frame you can mark it free by setting bit off in the bit map.