NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/os/linux/9843

Internet Message Format | 1992-09-04 | 3.3 KB

Path: sparky!uunet!mcsun!corton!jussieu!card
From: [e-mail] (Remy CARD)
Newsgroups: comp.os.linux
Subject: Re: efs - no bitmap?
Message-ID: <[e-mail]>
Date: 4 Sep 92 15:21:59 GMT
References: <[e-mail]>
Sender: [e-mail] (Le Facteur)
Organization: Laboratoire MASI - Universite Pierre et Marie Curie - Paris - France
Lines: 63
Nntp-Posting-Host: ares.ibp.fr

In article <[e-mail]> [e-mail] (bill davidsen) writes:
>
>  I was just looking through the README files for mcc 0.97p2 and noted
>that the efs claims to use a linked list instead of a bitmap, "saving
>all that wasted space" or some such. Since one of the major improvements
>between the original Sys5 filesystem and bsd/usf was changing from a
>linked list to a bitmap to reduce disk fragmentation and improve
>performance, I hope this doesn't mean what I think it does.

    Well, I think that I have to react.  Yes, I am going to disappoint you
but the ext fs really uses free inodes/blocks linked lists.  In fact, in
the linked list of free blocks, there is one list header per 256 free blocks:
the first free block contains the addresses of 254 other free blocks, which
can be addressed directly when the former block is in memory, and the address
of the next free block in the list which contains 254 addresses and so on.

>
>  Use of a linked list saves space, but you pay forever in performance,
>either by having fragmentation of by searching the list to insert newly
>freed disk space in order. In either case it's a bad idea and I hope
>that's not what is being used in efs. If it is someone should start
>working on efs2 now, but I assume the people who wrote efa knew about
>all this and the README is just unclear.

    I am not sure that a bitmap speeds up things: with a bitmap, you
have to load every block containing the bitmap until you find a bit set to
0.  Of course, you can keep the whole bitmap in memory but it means memory
waste if you mount a big fs.  With the current implementation of the ext fs,
the first block of the free list is always in memory so you can allocate
254 blocks without reading a block (the 254 blocks whose addresses are contained
in the first free block).  I think that it should be faster than the bitmap
scheme if you don't keep the bitmap in memory.

    Of course, this scheme may lead to some important seeks because blocks
can be allocated on different parts of the disk but I think that the problem
also exists if you use a bitmap.

    In fact, I think that performance can be improved in other ways.
I have been working on the new ext fs and I think that performance should
be better because :
    - it uses a cache used by lookup() which is called by namei().
      In fact, Linux (and other Un*x systems) spends a lot of time
      in namei() which converts a pathname to an inode number and
      and a cache really helps to get better performance,
    - bigger blocks may be supported so there will be less seek
      delays.  Fragments may also be supported to reduce disk
      space waste.

    I must admit that I have not made performance measurements yet.
I will do some soon and will try to tune the new ext fs to optimal
performance.


>
>--
>bill davidsen, GE Corp. R&D Center; Box 8; Schenectady NY 12345
>    I admit that when I was in school I wrote COBOL. But I didn't compile.


--

    Remy Card
    [e-mail]