About SFS (to Brendan)

[JJeronimo]

There is an error in the SFS spec... in section "Super-Block Format", paragraph 4 (ignoring the table), it says "This value must be equal to or greater than 2 (128 bytes per block or less is not supported).", but 2^(1 + 7)=256 (not 128). So, ti sould be "(256 bytes per block or less is not supported)"

JJ

[Combuster]

So, ti sould be "(256 bytes per block or less is not supported)"

or "This value must be equal to or greater than 1"

[JJeronimo]

So, ti sould be "(256 bytes per block or less is not supported)"

or "This value must be equal to or greater than 1"

Or so...



And there is an english mistake in the same section. At the beggining of paragraph 11, in the sentence "The size of the index area (at offset 0x01A4) indicates where the size of the index area in bytes,...", the word "where" doesn't make sense.

JJ

[Brendan]

Hi,

I've fixed both mistakes...

I changed it to "This value must be equal to or greater than 1", mostly because of the floppy disk controller which has an identical "bytes/sector" value, where 0x00 = 128 bytes or less per sector and starts getting messy, but 0x01 = 256 bytes per sector and is just as easy to work with as 512 byte sectors (or larger sectors).


Thanks,

Brendan

[JJeronimo]

Hi,

I've fixed both mistakes...

(...)

Thanks,

Not at all...

Have you already implemented SFS on any operating system? Or even as an user space program?


I think SFS has potential to go... for, example, OS support is an easy-to-achieve goal: just reduce the FS size by 5Meg and use the PC partition table to create a very small FAT FS at the end of the volume, which would then contain txt information and drivers for the most common OSs...

JJ

[JJeronimo]

I have a suggestion about time stamps... instead of using the proposed time stamp format, use Unununium Time... It's a 64-bit field, but it counts microseconds, and since 2000, not 1970... and it uses the International Atomic Time, instead of Universal Co-ordinated Time (i'm not sure of what it means in practise)

Alternatives:
I'm not very sure about the real benefits of using Uuutime... parhaps, the best choice would be counting the seconds since 1970, like Unix does, but in a quadword, in the intent of keeping the FS easy to implement...
Really, every OSdever will make the OS clock count seconds or something more accurate, but I doubt everyone is going to implement a nano or micro accuracy...
However, it's a matter of rounding down...

JJ

[JJeronimo]

What?! Data blocks in the same file must be continguous?!


Looks like the minios filesystem... where all files are single block!

http://hem.passagen.se/danma/

JJ

[Brendan]

Hi,

I have a suggestion about time stamps... instead of using the proposed time stamp format, use Unununium Time... It's a 64-bit field, but it counts microseconds, and since 2000, not 1970... and it uses the International Atomic Time, instead of Universal Co-ordinated Time (i'm not sure of what it means in practise)

There's a lot of different time formats that all vary slightly from each other in how they handle (or don't handle) leap seconds and other things. For physical media like disks, a difference of up to one second isn't very relevant due to the inaccuracy of timers used in computers. For example, the computer I'm using says it's 9:15 while my WinXP computer says the time is 11:53 (the clock on the wall says 12:54, and is probably the most accurate). If you compare your computer's time clock with something like this web site you'll probably notice some sort of variation.

In general, it doesn't really matter if SFS uses International Atomic Time/GPS time, UTC (with leap seconds), the incompatible POSIX variation of UTC (without leap seconds), or some other variation.

IMHO there's only really 2 things that are important. First, the time it uses isn't effected by things like daylight savings or time zones - this is fairly obvious.

Secondly, when a collection of files are copied from a computer to disk all of the timestamps for those files must be consistant. For example, if I have a script that modifies a file and then runs make, will the timestamp for the modified file be numerically lower than the time stamp for the file created by make? In some broken systems (Linux) the timestamp isn't accurate enough and there is no way to determine which file was modified first if they are both modified in the same second (i.e. the timestamps would be equal). Of course for a group of files copied from Linux the timestamps would have the same problem, but this shouldn't be the case if a group of files are copied from a "less-broken" (more accurate) OS.

I'm not very sure about the real benefits of using Uuutime... parhaps, the best choice would be counting the seconds since 1970, like Unix does, but in a quadword, in the intent of keeping the FS easy to implement...
Really, every OSdever will make the OS clock count seconds or something more accurate, but I doubt everyone is going to implement a nano or micro accuracy...
However, it's a matter of rounding down...

The original idea with the timestamps used by SFS is that they are easy to convert to Unix time format (seconds since 1970) by ignoring the lower 16 bits, while still providing better accuracy...


Cheers,

Brendan

[JJeronimo]

The original idea with the timestamps used by SFS is that they are easy to convert to Unix time format (seconds since 1970) by ignoring the lower 16 bits, while still providing better accuracy...

Right... Really, saying that the time is mesured in a power-of-two fraction of a second has the benefit of allowing round-downs by means of masking bits...

I don't have much idea of how many time formats are there...

JJ

[JJeronimo]

I've already implemented SFS on some operating system? Or even as an user space program?

This sentence doesn't make sense!

I'll edit the post...

JJ

[JJeronimo]

I think SFS has potential to go... for, example, OS support is an easy-to-achieve goal: just reduce the FS size by 5Meg and use the PC partition table to create a very small FAT FS at the end of the volume, which would then contain txt information and drivers for the most common OSs...

I'd not already read the section "Compatibility" section when I wrote this...
I'll post no more comments on SFS before I end reading the spec...

JJ

[Candy]

IMHO there's only really 2 things that are important. First, the time it uses isn't effected by things like daylight savings or time zones - this is fairly obvious.

Secondly, when a collection of files are copied from a computer to disk all of the timestamps for those files must be consistant. For example, if I have a script that modifies a file and then runs make, will the timestamp for the modified file be numerically lower than the time stamp for the file created by make? In some broken systems (Linux) the timestamp isn't accurate enough and there is no way to determine which file was modified first if they are both modified in the same second (i.e. the timestamps would be equal). Of course for a group of files copied from Linux the timestamps would have the same problem, but this shouldn't be the case if a group of files are copied from a "less-broken" (more accurate) OS.

I consider two things important:

- Are all time stamps generated in order? IE, you should not have time leaps where the time is adjusted to be "real", but where time stamps are duplicated. Bad implementations of some leap seconds can do this (doubly-giving out :59 to make for a leap second).
- Are all time stamps distinct? It's useful for a large number of events to determine both when something happened and to be able to give a definitive answer to "did this happen BEFORE or AFTER xyz".

The latter is mainly for inside-computer communication, so it needn't be saved to disk. My OS is going to use an all-inclusive 64-bit or 128-bit timer (think 64-bit) where the lower 16/64 bits are for sub-second precision (and incrementing for uniquity).

[Brendan]

Hi,

I consider two things important:

- Are all time stamps generated in order? IE, you should not have time leaps where the time is adjusted to be "real", but where time stamps are duplicated. Bad implementations of some leap seconds can do this (doubly-giving out :59 to make for a leap second).
- Are all time stamps distinct? It's useful for a large number of events to determine both when something happened and to be able to give a definitive answer to "did this happen BEFORE or AFTER xyz".

Unfortunately, (according to Wikipedia) systems with strict POSIX compliance do have the same times twice when leap seconds are added. This means you can get the time and 500 ms later get an earlier time.

In general there's 2 different ways of defining time.

If a second is exactly 1/86400 of a day, then because the length of days and years varies you end up with "variable length seconds", which is good for accurately measuring large amounts of time because there's no complicated calculations, but bad for accurately measuring small amounts of time. I'd call this "solar time".

Alternatively, if a second is always the same length of time, then you end up with a variable number of seconds per day. This is good for accurately measuring small amounts of time, but accurately measuring large amounts of time becomes complicated. This method is used for the standard "SI second".

UTC is a compromise between these approaches - SI seconds with occasional adjustments to make it match solar time.

The latter is mainly for inside-computer communication, so it needn't be saved to disk. My OS is going to use an all-inclusive 64-bit or 128-bit timer (think 64-bit) where the lower 16/64 bits are for sub-second precision (and incrementing for uniquity).

My last version used a "64:32 fixed point integer" - a system-wide 64-bit integer that was used to keep track of ms since 2000, combined with a 32-bit "factions of a millisecond" value used internally by the timer IRQ to compensate for drift, etc. I used true UTC time (with leap seconds), and hid the complexity of calculations inside the kernel API.

One problem with this is accurately calculating times 6 months or more ahead without knowing if a leap second will be added to UTC in advance, which could lead to calculations being incorrect by a maximum of one second per year. IMHO this isn't a huge problem as these long range calculations rarely need so much accuracy, and it's possible to postpone the calculation until just before it's needed to avoid the inaccuracy

The other problem is informing the OS when a leap second will be added - I assumed there'd be some sort of software updates happening every few months (which may be a bad assumption for some people).

The other main hurdle for accurate time keeping is handling large corrections. If the user notices that the time is wrong and wants to increase or decrease it by 10 minutes, then do you allow a sudden change (and mess up running software), or do you gradually compensate (e.g. increase the time counter at a rate of 1.01 Hz or 0.99 Hz instead of 1 Hz until the time is correct again) to avoid the sudden change. What if the user reboots and changes the RTC time using the BIOS? A file saved 5 minutes ago could look like it was saved a long time in the past or a long time in the future. For me, this becomes much more difficult because there's also the added problem of keeping all computers in the cluster synchronized. To be honest, I haven't really found a solution for these problems that I like...


Cheers,

Brendan

[smiddy]

Brendan,

I suspect you're coming at this from a security perspective, yes?

I don't know that keeping time in the kernal is needed. We're talking desktops and not computers performing realtime precision either, right? If an application needs precision that application could build it into their own code and not rely on the OS API for their precision. Unless you're mapping stars and doing astrophysics with your computer I think you could use a connection to NIST or some other time keeper to ping for time every so often to make certain you don't skew too much, by using the RTC. File dates will happen when they happen.

But, if you're concerned with accurate time for reasons of security and computer forensics then you have to have a redundant system that applies anti-tamper measures also, besides the continued precision due to changes in orbit of Earth around the sun. And then you'd really have to consider the precision need to make a case...I think within a second is fine enough, but others might thing that nano seconds are where they want to be, then things do get messy, and a solution to the whimsical changes in Earth's orbit are less predictable beyond (going to the right or greater precisions between metronomes) a second in time.

Sorry, I don't offer a solution you're looking for, but I think it is wise to consider the application of time and the requirements for its use, then implement something that meets the requirement and nothing more.

[Brendan]

Hi,

I don't know that keeping time in the kernal is needed. We're talking desktops and not computers performing realtime precision either, right? If an application needs precision that application could build it into their own code and not rely on the OS API for their precision. Unless you're mapping stars and doing astrophysics with your computer I think you could use a connection to NIST or some other time keeper to ping for time every so often to make certain you don't skew too much, by using the RTC. File dates will happen when they happen.

For me, there's a single time counter (and single time format) that is used for everything, including measuring how much CPU time each thread has consumed, setting time delays (including very small delays for device drivers), the basis for "cron", etc.

Some examples:

Code: Select all

main() {
    doDialog_getString("What do you want to be reminded of?\n", &reminderString);
    doDialog_getTime("When should you be reminded?\n", year, month, day, hour, minute);
    time = kernelAPI_convertLocalTimeToSystemTime(year, month, day, hour, minute, 0, 0);
    kernelAPI_sleepUntil(time);
    doDialog_showString(&reminderString);
}

Code: Select all

#define DELAY_30MILLISECONDS    30000

videoUpdateThread() {
    nextTime = kernelAPI_getTime();
    for(;;) {
        drawTheNextVideoFrame();
        nextTime += DELAY_30MILLISECONDS;
        kernelAPI_sleepUntil(nextTime);
    }
}

Code: Select all

main() {
    maxTests = 16;
    startTime = kernelAPI_getTime();
    for(i = 0; i < maxTests; i++) {
        doTest();
    }
    totalTime = kernelAPI_getTime() - startTime;
    printf("The function took an average of %d micro-seconds\n", totalTime / maxTests);
}

But, if you're concerned with accurate time for reasons of security and computer forensics then you have to have a redundant system that applies anti-tamper measures also, besides the continued precision due to changes in orbit of Earth around the sun. And then you'd really have to consider the precision need to make a case...I think within a second is fine enough, but others might thing that nano seconds are where they want to be, then things do get messy, and a solution to the whimsical changes in Earth's orbit are less predictable beyond (going to the right or greater precisions between metronomes) a second in time.

Simply getting correct behaviour is hard enough. For an example, try "make foo", then reboot your computer and use the BIOS to set the time to last week, then do "touch somefile" and then try "make foo" again. What if you're doing incremental backups? For some OSs, you get the same problems even when you use the OS to change the current time.

Now consider what happens if a thread does "sleep(DELAY_30MILLISECONDS)" and the user changes the time from "10:00 AM" to "5:00 AM" before the thread wakes up. Will the kernel handle it correctly, or will the thread sleep for 5 hours too long? What if the hard disk driver does "sleep(DELAY_30MILLISECONDS)"?

For accuracy; the accuracy for short time periods is important (especially for things like hardware delays, measuring used CPU time, etc). Lately I've been porting/rewriting some compression/decompression code which reports how long it took to compress or decompress. On Linux, often my code defies all the laws of physics and completes instantly (in reality it takes less than "10-ish-milliseconds", and Linux is too crappy to measure it properly).

The accuracy for long time periods isn't that important - if you want to wait for 3 years and you actually wait for 3 years and one second, I doubt it's going to matter.

Of course there is another important factor - to be able to say that my OS is better than <insert_any_other_OS_here> because <insert_some_reason_here>....


Cheers,

Brendan