UFS fragments - Unix

This is a discussion on UFS fragments - Unix ; Hello Group, I have a few questions dealing with UFS and block fragments. 1. How does UFS deal with fragments of a block? 2. What if a file occupies multiple block fragments? 3. And how does the kernel keep track ...

+ Reply to Thread
Results 1 to 6 of 6

Thread: UFS fragments

  1. UFS fragments


    Hello Group,

    I have a few questions dealing with UFS and block fragments.

    1. How does UFS deal with fragments of a block?

    2. What if a file occupies multiple block fragments?

    3. And how does the kernel keep track of them?


    I'm writing a filesystem for USB devices called usbfs. This is designed
    for application use only. All the kernel will know about is that a
    program is directly accessing a raw device using an exclusive lock. My
    routines will do all caching and buffering internally.

    I'm seriously thinking of modeling it after the UFS filesystem, but I'm
    open to suggestions. Right now, my storage overhead is 227 sectors out
    of 512,000 sectors for a 256MB storage device. The current breakdown is
    as follows:

    512,000 = 64000 bytes in the allocation bitmap.

    sector 0 - partition table
    sector 1 - GUID control data

    And from here...

    1 sector - block fragment list (64 per sector)
    1 sector - defect list (64 per sector)
    2 sectors - dir entries (32 per sector)
    32 sectors - inode data (2 per sector) total 64 inodes.
    64 sectors - swap sectors for defects
    125 sectors - allocation bitmap

    Should I go this route or is there a better way?

    --
    Daniel Rudy

    Email address has been base64 encoded to reduce spam
    Decode email address using b64decode or uudecode -m

    Why geeks like computers: look chat date touch grep make unzip
    strip view finger mount fcsk more fcsk yes spray umount sleep

  2. Re: UFS fragments

    Daniel Rudy writes:
    > I have a few questions dealing with UFS and block fragments.
    >
    > 1. How does UFS deal with fragments of a block?


    It has the ability to break blocks down to 512 byte fragments. That's
    the source of the original 2TB limit -- 2^32 addressable fragments.

    > 2. What if a file occupies multiple block fragments?


    I'm not sure what you mean. Fragments (if any exist) are always at
    the end of the file and (additionally) only exist for files that don't
    have indirect blocks.

    So, a file on a file system with 4096-byte blocks and 512-byte
    fragments can have from 0 to 7 fragments at the end. They're all
    contiguous in the same block.

    > 3. And how does the kernel keep track of them?


    By fragment number ... ?

    I suspect you might be thinking that fragments can be arbitrarily
    littered throughout the file. This is not so. Instead, the very last
    direct block points to a contiguous set of fragments, limited by file
    size. This is the only set of fragments in a file.

    > Should I go this route or is there a better way?


    Are you doing this on any particular operating system, or does that
    not matter?

    I think you may find quite a few file system implementations around
    that could be adapted, rather than writing a new one.

    --
    James Carlson, Solaris Networking
    Sun Microsystems / 1 Network Drive 71.232W Vox +1 781 442 2084
    MS UBUR02-212 / Burlington MA 01803-2757 42.496N Fax +1 781 442 1677

  3. Re: UFS fragments

    At about the time of 4/4/2007 5:37 AM, James Carlson stated the following:
    > Daniel Rudy writes:
    >> I have a few questions dealing with UFS and block fragments.
    >>
    >> 1. How does UFS deal with fragments of a block?

    >
    > It has the ability to break blocks down to 512 byte fragments. That's
    > the source of the original 2TB limit -- 2^32 addressable fragments.
    >


    I gathered that 2.1TB limit in my calculations as well. I seriously
    doubt that any USB thumb/flash drive will be exceeding 2.1TB anytime soon.

    >> 2. What if a file occupies multiple block fragments?

    >
    > I'm not sure what you mean. Fragments (if any exist) are always at
    > the end of the file and (additionally) only exist for files that don't
    > have indirect blocks.


    I see. So only a direct pointer from an inode can reference a
    fragmented block then.

    > So, a file on a file system with 4096-byte blocks and 512-byte
    > fragments can have from 0 to 7 fragments at the end. They're all
    > contiguous in the same block.


    Ok.

    >> 3. And how does the kernel keep track of them?

    >
    > By fragment number ... ?


    So it records the block number that is fragmented and which fragments of
    the block are in use? It would have to if it was to find it again.

    > I suspect you might be thinking that fragments can be arbitrarily
    > littered throughout the file. This is not so. Instead, the very last
    > direct block points to a contiguous set of fragments, limited by file
    > size. This is the only set of fragments in a file.


    And you would be right, so that clears it up. Now this brings up
    another question. Can you have 2 files share the same fragmented block?
    For example, file 1 fragments on block 226, using fragment 0, 1, and 2.
    File 2 also fragments on block 226 and uses fragments 3 and 4.
    Fragments 5, 6, and 7 are unallocated. Does UFS do this?

    >> Should I go this route or is there a better way?

    >
    > Are you doing this on any particular operating system, or does that
    > not matter?


    Specifically? FreeBSD, but it *should* run on any posix compliant Unix
    operating system.

    > I think you may find quite a few file system implementations around
    > that could be adapted, rather than writing a new one.


    My issue is maximizing the data storage space with as little overhead as
    possible, along with the security of utilizing a non-standard
    filesystem. I am designing it for applications that utilize large
    amounts of archival data that doesn't change very much and have various
    security requirements. IOW, you don't have to mount the device onto the
    filesystem for the application to use it.

    --
    Daniel Rudy

    Email address has been base64 encoded to reduce spam
    Decode email address using b64decode or uudecode -m

    Why geeks like computers: look chat date touch grep make unzip
    strip view finger mount fcsk more fcsk yes spray umount sleep

  4. Re: UFS fragments

    Daniel Rudy writes:
    > >> 2. What if a file occupies multiple block fragments?

    > >
    > > I'm not sure what you mean. Fragments (if any exist) are always at
    > > the end of the file and (additionally) only exist for files that don't
    > > have indirect blocks.

    >
    > I see. So only a direct pointer from an inode can reference a
    > fragmented block then.


    Right.

    > >> 3. And how does the kernel keep track of them?

    > >
    > > By fragment number ... ?

    >
    > So it records the block number that is fragmented and which fragments of
    > the block are in use? It would have to if it was to find it again.


    No.

    It just records the block number. Block numbers are themselves
    fragment indices -- it's the same thing.

    And it doesn't need to know which fragments are in use, because the
    file size from the directory entry tells you that exactly.

    So, for a really simple example, consider a file that is 4609 bytes
    long. The first 4096 bytes take up a full block (assuming fs_bsize ==
    4096). The first direct block points to (say) 12016.

    The next 513 bytes take up two fragments (one with 512 bytes, and one
    with 1 byte). The second direct block points to (say) 12024. This is
    the next adjacent location on the disk -- because block numbers are
    counted in fragments, 4096/512 == 8, and 12016+8 == 12024.

    This leaves block (fragment) numbers 12026-12031 open for data from
    other files.

    > > I suspect you might be thinking that fragments can be arbitrarily
    > > littered throughout the file. This is not so. Instead, the very last
    > > direct block points to a contiguous set of fragments, limited by file
    > > size. This is the only set of fragments in a file.

    >
    > And you would be right, so that clears it up. Now this brings up
    > another question. Can you have 2 files share the same fragmented block?


    Sure.

    > For example, file 1 fragments on block 226, using fragment 0, 1, and 2.
    > File 2 also fragments on block 226 and uses fragments 3 and 4.
    > Fragments 5, 6, and 7 are unallocated. Does UFS do this?


    Yes.

    > >> Should I go this route or is there a better way?

    > >
    > > Are you doing this on any particular operating system, or does that
    > > not matter?

    >
    > Specifically? FreeBSD, but it *should* run on any posix compliant Unix
    > operating system.


    OK.

    > > I think you may find quite a few file system implementations around
    > > that could be adapted, rather than writing a new one.

    >
    > My issue is maximizing the data storage space with as little overhead as
    > possible, along with the security of utilizing a non-standard
    > filesystem. I am designing it for applications that utilize large
    > amounts of archival data that doesn't change very much and have various
    > security requirements. IOW, you don't have to mount the device onto the
    > filesystem for the application to use it.


    That sounds like security-by-obscurity to me. I would certainly not
    recommend it as a useful design pattern, as it just begs for cracking
    -- and it sounds like just trawling through the data without knowing
    the FS layout would reveal sensitive information.

    Instead, if you need useful security, investigate ways to encrypt your
    data. Most modern OSes have some easily-available means to encrypt
    data using cryptographically strong algorithms, as well as mechanisms
    that can store and protect your keys for you.

    But, before you do that, you'll likely want to engage some folks who
    can analyze your security situation. Security is a rather subtle
    area, and it's quite easy for folks without extensive experience to
    fall into nasty traps.

    Better still, find an already worked-out encryption solution, and use
    that.

    As for the mounting issue, that's usually taken care of by some sort
    of privilege-granting mechanism. But if you want to hack it in user
    space instead, I'd suggest considering reusing something like FUSE.

    --
    James Carlson, Solaris Networking
    Sun Microsystems / 1 Network Drive 71.232W Vox +1 781 442 2084
    MS UBUR02-212 / Burlington MA 01803-2757 42.496N Fax +1 781 442 1677

  5. Re: UFS fragments

    At about the time of 4/5/2007 8:42 AM, James Carlson stated the following:
    > Daniel Rudy writes:
    >>>> 2. What if a file occupies multiple block fragments?
    >>> I'm not sure what you mean. Fragments (if any exist) are always at
    >>> the end of the file and (additionally) only exist for files that don't
    >>> have indirect blocks.

    >> I see. So only a direct pointer from an inode can reference a
    >> fragmented block then.

    >
    > Right.
    >
    >>>> 3. And how does the kernel keep track of them?
    >>> By fragment number ... ?

    >> So it records the block number that is fragmented and which fragments of
    >> the block are in use? It would have to if it was to find it again.

    >
    > No.
    >
    > It just records the block number. Block numbers are themselves
    > fragment indices -- it's the same thing.
    >
    > And it doesn't need to know which fragments are in use, because the
    > file size from the directory entry tells you that exactly.
    >
    > So, for a really simple example, consider a file that is 4609 bytes
    > long. The first 4096 bytes take up a full block (assuming fs_bsize ==
    > 4096). The first direct block points to (say) 12016.
    >
    > The next 513 bytes take up two fragments (one with 512 bytes, and one
    > with 1 byte). The second direct block points to (say) 12024. This is
    > the next adjacent location on the disk -- because block numbers are
    > counted in fragments, 4096/512 == 8, and 12016+8 == 12024.
    >
    > This leaves block (fragment) numbers 12026-12031 open for data from
    > other files.
    >


    Well this adds a whole new dimension to the discussion. If blocks are
    fragments anyways, then why even have blocks at all?

    >>> I suspect you might be thinking that fragments can be arbitrarily
    >>> littered throughout the file. This is not so. Instead, the very last
    >>> direct block points to a contiguous set of fragments, limited by file
    >>> size. This is the only set of fragments in a file.

    >> And you would be right, so that clears it up. Now this brings up
    >> another question. Can you have 2 files share the same fragmented block?

    >
    > Sure.
    >


    Ok.

    >> For example, file 1 fragments on block 226, using fragment 0, 1, and 2.
    >> File 2 also fragments on block 226 and uses fragments 3 and 4.
    >> Fragments 5, 6, and 7 are unallocated. Does UFS do this?

    >
    > Yes.
    >


    Ok.

    >>>> Should I go this route or is there a better way?
    >>> Are you doing this on any particular operating system, or does that
    >>> not matter?

    >> Specifically? FreeBSD, but it *should* run on any posix compliant Unix
    >> operating system.

    >
    > OK.
    >
    >>> I think you may find quite a few file system implementations around
    >>> that could be adapted, rather than writing a new one.

    >> My issue is maximizing the data storage space with as little overhead as
    >> possible, along with the security of utilizing a non-standard
    >> filesystem. I am designing it for applications that utilize large
    >> amounts of archival data that doesn't change very much and have various
    >> security requirements. IOW, you don't have to mount the device onto the
    >> filesystem for the application to use it.

    >
    > That sounds like security-by-obscurity to me. I would certainly not
    > recommend it as a useful design pattern, as it just begs for cracking
    > -- and it sounds like just trawling through the data without knowing
    > the FS layout would reveal sensitive information.


    Not really...see below.

    > Instead, if you need useful security, investigate ways to encrypt your
    > data. Most modern OSes have some easily-available means to encrypt
    > data using cryptographically strong algorithms, as well as mechanisms
    > that can store and protect your keys for you.
    >
    > But, before you do that, you'll likely want to engage some folks who
    > can analyze your security situation. Security is a rather subtle
    > area, and it's quite easy for folks without extensive experience to
    > fall into nasty traps.
    >
    > Better still, find an already worked-out encryption solution, and use
    > that.


    Too late.

    I already came up with something that works pretty well. The data
    itself is encrypted with AES-512. I just want one more layer to make it
    hard to get at the data.

    > As for the mounting issue, that's usually taken care of by some sort
    > of privilege-granting mechanism. But if you want to hack it in user
    > space instead, I'd suggest considering reusing something like FUSE.
    >


    FUSE? Hmm... I just now checked it out when you mentioned it. It's a
    KLM. I want this to be completely self contained within the application
    itself. Hence the reason why I'm writing it from scratch.

    --
    Daniel Rudy

    Email address has been base64 encoded to reduce spam
    Decode email address using b64decode or uudecode -m

    Why geeks like computers: look chat date touch grep make unzip
    strip view finger mount fcsk more fcsk yes spray umount sleep

  6. Re: UFS fragments

    Daniel Rudy writes:
    > At about the time of 4/5/2007 8:42 AM, James Carlson stated the following:
    > > This leaves block (fragment) numbers 12026-12031 open for data from
    > > other files.
    > >

    >
    > Well this adds a whole new dimension to the discussion. If blocks are
    > fragments anyways, then why even have blocks at all?


    Because it's far more efficient to have a single direct or indirect
    block entry to refer to a group of 8 fragments than to have refer to
    each fragment individually, and because blocks are always aligned on
    stronger boundaries (4096, usually) than fragments (512) and thus are
    more efficient for I/O.

    > I already came up with something that works pretty well. The data
    > itself is encrypted with AES-512. I just want one more layer to make it
    > hard to get at the data.


    It sounds like you might be making things hard on yourself. Do you
    really want to be in the file system development business? Is that
    the product you're building?

    > > As for the mounting issue, that's usually taken care of by some sort
    > > of privilege-granting mechanism. But if you want to hack it in user
    > > space instead, I'd suggest considering reusing something like FUSE.
    > >

    >
    > FUSE? Hmm... I just now checked it out when you mentioned it. It's a
    > KLM. I want this to be completely self contained within the application
    > itself. Hence the reason why I'm writing it from scratch.


    FUSE is several things. There's a kernel module, so that ordinary
    file system activity gets redirected to user space via a well-known
    plug-in API, but the user space part has full file systems implemented
    in it.

    Thus, the idea I was suggesting was that you could implement the FUSE
    plug-in API in your application, and then use one of the plug-in file
    systems rather than rolling your own.

    It seems to me like that ought to work.

    --
    James Carlson, Solaris Networking
    Sun Microsystems / 1 Network Drive 71.232W Vox +1 781 442 2084
    MS UBUR02-212 / Burlington MA 01803-2757 42.496N Fax +1 781 442 1677

+ Reply to Thread