You just need to keep track of overflow -- something like this will
work (I'm unfamiliar with the _[x] notation used.. is it special?):
uint32_t max(uint32_t a, uint32_t b) {
if (a >= b) {
return a;
}
return b;
}
uint128_t add128(uint128_t a, uint128_t b) {
uint128_t retval;
uint32_t count,overflow = 0;
for (count = 0; count < 4; count++) {
retval._[count] = overflow + a._[count] + b._[count];
if (retval._[count] < max(a,b)) {
overflow = 1;
} else {
overflow = 0;
}
}
return retval;
}
There's code for a thing called safeint, which I've heard of but never
used, perhaps you should give that a look. Also, I'm certain there are
more efficient ways to do what I've done, this is just an example.
Finally, endianness is very important here - I've assumed little endian,
but your filesystem might not be.
On Mon, Jan 04, 2010 at 09:15:24PM -0800, Bhaktavatsalam Nallanthighal wrote:
> Hey back,
>
> Once again, you exactly nailed my problem. The main reason I'm
> concerned with this issue is because I'm trying to implement a 128-bit
> Database Filesystem. The explanation and example you provided were
> helpful, but please allow me to probe you a little more. Okay, now
> with the method you described, I have a 128-bit value.
>
> Staying along the lines of the solution you proposed and if I am not
> wrong, Prof.Andrew Tanenbaum's Minix Source code has a 64-bit datatype
> somewhere, that is just a struct containing an array of two uint32's,
> something like this:
>
> typedef struct { uint32_t _[2]; } uint64_t;
>
> In the similar way, I can achieve an 128-bit datatype in C using an
> array of four 32-bit datatypes [to keep things familiar to me, not 2
> 64-bit]. It would be something like this:
>
> typedef struct { uint32_t _[4]; } uint128_t;
>
> Suppose I stick to C to keep my filesystem implementation low-level-
> transparent and clear to me [it is part of a larger project that is
> being written in C], instead of using C++ [implying that I don't want
> to overload my operators], and I want to add two 128-bit numbers. Say,
> in my context, that before unmounting my filesystem, I want to perform
> a CRC Checksum of my filesystem parameters[just like how a CRC is done
> with Internet Datagram Headers before pushing them to lower levels]
> and store it in a Parameter block to mark the partition not-dirty. As
> my filesystem is 128-bit, I will have to add several 128-bit numbers,
> how would I accomplish this?
>
> Thanks once again, for all your time and suggestions.
>
> Bhaktavatsalam Nallanthighal
>
>
> On Jan 4, 5:58 pm, [email protected] wrote:
> > Unfortunately, you're not talking to a filesystem expert. I know that
> > actual address space (memory and memory-mapped files) cannot exceed the
> > addressing capability of the processor i.e. 32 bit systems can only address
> > 4GB memory, which causes trouble if you try to mmap a file larger than
> > 4GB - this is common for database applications. Filesystems, on the
> > other hand, aren't mapped to memory. You can address a 128 bit memory
> > location as four 32-bit memory locations. For example, assume the
> > address is held in dx:ds, and you're loading the data into four 32 bit
> > registers:
> >
> > mov eax, dx:ds
> > mov reg1, eax
> > incf ds
> > mov eax, dx:ds
> > .
> > .
> > .
> > mov reg4, eax
> >
> > And now reg1:reg2:reg3:reg4 will have 128 bits of data, 1 memory address
> > location from the filesystem. I haven't used assembly in awhile, and
> > the last time I did it was on the PIC, so my syntax above is probably
> > wrong, but I hope it gets the idea across. In reality, you'd probably
> > do a table read into contiguous memory from the disk, which would
> > optimize the operation, but I'd have to look up how to do that :)
> >
> > So, you see, the 32-bit limitation limits only memory address space and
> > instruction size, but doesn't strictly limit files (unix treats nearly
> > everything as a file, so disks, and their filesystems, are files.)
> >
> > Anybody know of a good OS development list? Because this question is
> > getting rather technical, and beyond the scope of a linux users group,
> > into a developers group.
> >
> > On Mon, Jan 04, 2010 at 02:44:06PM -0800, Bhaktavatsalam Nallanthighal
> > wrote:
> > > Hi back,
> >
> > > I appreciate that reply. You really nailed my problem. As you've
> > > said, I'm confused with instruction size and address space. However,
> > > I'm more confused about the sizes of the data the instructions operate
> > > on rather than the instruction size itself [did you mean the way the
> > > instruction opcodes are CISC packed by "instruction size"?]. Your
> > > reply in an overall sense was helpful, but was too general for me to
> > > do anything useful "programmatically". Can you elaborate on how 128-
> > > bit addresses can be accessed using normal 32-bit instructions
> > > [assuming that you have that much memory?]? If you can provide a
> > > simple example, I'd be really really thankful to you. Any pointers
> > > would also be appreciated.
> >
> > > Bhaktavatsalam Nallanthighal
> >
> > > On Jan 4, 10:19�am, [email protected] wrote:
> > > > On Mon, Jan 04, 2010 at 01:27:06AM -0800, Bhaktavatsalam Nallanthighal
> > > > wrote:
> > > > > Hi,
> >
> > > > > Thanks for the elaborate reply and for the pointer. I've been reading
> > > > > various parts of an old Linux kernel, Minix and Unix V 6.0. This is
> > > > > along the lines of writing my own kernel. You said that conditional
> > > > > compilation is used for various architecture specific features. As
> > > > > you've suggested, this is evident from the kernel's coding if it is
> > > > > supporting a wide range of processors [the preprocessing] But, the
> > > > > more confusing point to me is how the kernel is able to consistently
> > > > > do this across varying architectures. For example, if linux kernel
> > > > > supports a processor that has no protection features or atleast not as
> > > > > many as Intel processors have, how would the overall impact be
> > > > > managed.
> >
> > > > > For Instance, say that the linux kernel is using the protection
> > > > > features of the Intel processor to keep user-space programs from
> > > > > affecting the kernel [which seems to me as the most natural way to do.
> > > > > If otherwise, please mention]. If the kernel is able to run on some
> > > > > other architecture that does not have these features, does it mean
> > > > > that it offers no protection? Or does it mean that protection is
> > > > > implemented in software for that processor.
> >
> > > > > Another Instance, say that the linux kernel supports multitasking
> > > > > using the hardware features of the Intel processors[TSSes etc. Please
> > > > > correct me if this is not the way, again.] How is this able to port
> > > > > across some other architecture that does not have these features in
> > > > > hardware? Is it implemented in software?
> >
> > > > > Apart from this, I would be helpful if more clarification can be
> > > > > provided on the issue with supporting higher level datatypes and
> > > > > different sized-processors. The exact issue is with how linux supports
> > > > > higher types during RUNTIME. A best example to represent the issue, is
> > > > > with ZFS. I heard somewhere that ZFS[from Sun] is supported on linux.
> > > > > But, it is well known that ZFS is a 128-bit file system. If the
> > > > > processor is able to only manipulate data in 32-bit, how are 128-bit
> > > > > operations like addition, subtraction done? Are there any cascadable-
> > > > > instructions that provide a carry/borrow/etc. so that each 128-bit
> > > > > operations require four 32-bit operations? If so, isn't this very
> > > > > inefficient?
> >
> > > > > You also said that the system calls provide a unified layer to other
> > > > > parts of the kernel. Do you mean that each system call is differently
> > > > > implemented for each kind of processor? For example, consider kmalloc
> > > > > () function. Is kmalloc() implemented differently for each processor?
> >
> > > > > I'm just few steps away from diving into a linux book. I'm just trying
> > > > > to avoid it as much as possible, through asking people due to time
> > > > > restrictions. Additionally, the website you provided is nice. Good
> > > > > article on Portable device drivers.
> >
> > > > > Bhaktavatsalam Nallanthighal
> >
> > > > > On Jan 4, 2:11 am, Sid <[email protected]> wrote:
> > > > > > On Jan 4, 5:34 am, Bhaktavatsalam Nallanthighal
> >
> > > > > > <[email protected]> wrote:
> > > > > > > Hello,
> >
> > > > > > > Can anyone explain in a clear way, how linux deals with
> > > > > > > portability across architectures. The main points I'm getting
> > > > > > > confused
> > > > > > > are:
> >
> > > > > > > - Does a single linux kernel support processors of varying size? I
> > > > > > > mean, will the same linux kernel give me the ability to compile
> > > > > > > it for
> > > > > > > various sized processors[8-bit, 16-bit, 32-bit, 64-bit]?
> >
> > > > > > Yes, linux kernel supports different processors. Although I am not
> > > > > > sure if it supports an 8 bit one, as linux was first made for 80386
> > > > > > microprocessor.
> > > > > > If you configure and compile the kernel yourself, you'll see that
> > > > > > there are options that allow you to compile it for different
> > > > > > processors. These options are nothing but conditional compilation
> > > > > > statements like #ifdef in the kernel code, so, according to the
> > > > > > processor you select, the coressponding code for that very processor
> > > > > > is compiled.
> >
> > > > > > > If so, how
> > > > > > > does it deal with the datatypes consistently?
> >
> > > > > > There is definition for different datatypes and again conditional
> > > > > > compilation is used for the same. If you go through the kernel code
> > > > > > you'll see that there are various directories for different
> > > > > > architectures. e.g. for x86 machines, you'll find the code in arch/
> > > > > > x86/.
> >
> > > > > > > And how does it provide
> > > > > > > a unified layer to applications that use processor specific
> > > > > > > functionality?
> >
> > > > > > System Calls, and the library functions help you do that.
> >
> > > > > > >Also, how does it manupilate datatypes that the
> > > > > > > processor does not inherently support. For example, if I am able
> > > > > > > to
> > > > > > > compile for a 16-bit processor, how does it support the uint32
> > > > > > > datatype used in other areas of the kernel [addition, subtraction,
> > > > > > > byte ordering]?
> >
> > > > > > I guess gcc does that for you. Please let me know if I am wrong
> > > > > > here.
> >
> > > > > > > - Does the Linux kernel implement "Protected Mode" and other kinds
> > > > > > > of features also in other architectures that do not support them?
> > > > > > > If so, how? If not, how is it made possible that one feature is
> > > > > > > present
> > > > > > > in one compilation and is not present in another? How does this
> > > > > > > effect
> > > > > > > the other areas of the kernel that depend on this features
> >
> > > > > > No it doesn't on other processors. And once again conditional
> > > > > > compilation is used for that.
> >
> > > > > > > Thanks in advance. If possible please send me your replies to
> > > > > > > [email protected]. The digests I get fill my inbox!
> >
> > > > > > > Bhaktavatsalam Nallanthighal
> >
> > > > > > Also, if you've already not done it, configure and compile the
> > > > > > kernel
> > > > > > yourself, you'll know how things actually work. Also read the kernel
> > > > > > sources. If you're interested to know about the Linux kernel a great
> > > > > > place to start ishttp://kernelnewbies.org/.
> >
> > > > > --
> > > > > You received this message because you are subscribed to the Linux
> > > > > Users Group.
> > > > > To post a message, send email to [email protected]
> > > > > To unsubscribe, send email to
> > > > > [email protected]
> > > > > For more options, visit our group
> > > > > athttp://groups.google.com/group/linuxusersgroup
> >
> > > > Well, you're confusing instruction size with address space. The
> > > > instructions use a 32-bit instruction, while the address space (although
> > > > 32 bit) can be manipulated to 128 bits. �While it is technically less
> > > > efficient to access 128-bit addresses with 64 or 32 bit address spaces,
> > > > it is quite possible and the performance hit isn't *that* bad. �It's
> > > > not
> > > > a matter of using 4 32-bit instructions to fire one 128-bit
> > > > instruction, it's a
> > > > matter of using 4 32-bit cpu registers to hold one 128-bit address, and
> > > > using clever techniques to efficiently address the data. �You should
> > > > look into memory segmentation in assembler to get a better idea
> > > > for how this works.
> >
> > > --
> > > You received this message because you are subscribed to the Linux Users
> > > Group.
> > > To post a message, send email to [email protected]
> > > To unsubscribe, send email to [email protected]
> > > For more options, visit our group
> > > athttp://groups.google.com/group/linuxusersgroup
> >
> >
>
> --
> You received this message because you are subscribed to the Linux Users Group.
> To post a message, send email to [email protected]
> To unsubscribe, send email to [email protected]
> For more options, visit our group at
> http://groups.google.com/group/linuxusersgroup
--
You received this message because you are subscribed to the Linux Users Group.
To post a message, send email to [email protected]
To unsubscribe, send email to [email protected]
For more options, visit our group at
http://groups.google.com/group/linuxusersgroup
