Unix v6 Ported to ANSI C | Hacker News Reader

Unix v6 Ported to ANSI C

os-blog.com

224 pointsoctopus50 comments

There is a bug in the memmove() function from ulib.c:

    void*
    memmove(void *vdst, void *vsrc, int n)
    {
      char *dst, *src;
  
      dst = vdst;
      src = vsrc;
      while(n-- > 0)
        *dst++ = *src++;
      return vdst;
    }

If the two blocks overlap, and the address of dst is greater than the address of src, then parts of the source will be overwritten before it can be copied.

reminds me of the intel comment in their implementation of memcpy, something like 'no overlay check as implicit convention'

Yes, the standards say that the behavior of memcpy, as opposed to memmove, is undefined when the arguments overlap.

The original v6 doesn’t have any of the mem* functions, but its bcopy implementation has the same issue. Presumably the convention that bcopy permits overlap had not been established at that time.

Right. Quoting from the manpage:

> The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.

http://www.kernel.org/doc/man-pages/online/pages/man3/memmov...

Notice how it says 'as though'; I can't see why doing the copy backwards (from end to start) wouldn't work, myself.

Still doesn't work going end to start.

    src starts at 50, ends at 100
    dst starts at 25, ends at 75.

First we copy 100 to 75, then 99 to 74, etc ... now we get to copy from 75 to 50, but we've overwritten it already!

If it's higher, move from the front. If it's lower, start at the back. You have to check each time you do it.

Linux isn't Unix, so are you sure it's the same?

memmove() is in ANSI C standard.

UNIX v6 predates ANSI C by over a decade I think.

I'm not massively great at C but would this be a fix?

    void*
    memmove(void *vdst, void *vsrc, int n)
    {
        char *dst, *src;

        dst = vdst;
        src = vsrc;
        if(*vdst > *vsrc) {
            *vdst += n;
            *vsrc += n;
            while(n-- > 0)
                *dst-- = *src--;
        }
        else if(*vdst < *vsrc)
            while(n-- > 0)
                *dst++ == *src++;
        return vdst;
    }

At least two bugs: the test should compare vdst to vsrc, not * vdst to * vsrc, and in the first branch you're copying vsrc[n] which is out of range (and skipping vsrc[0]).

The first bug I'm confused? Surely we want to use the * because we're comparing the position in memory, not what's in the memory? Or does the * mean "compare what is in that memory slot"?

Second bug, cheers.

http://news.ycombinator.com/item?id=3214807

I see an additional bug in there compared to the original, you're copying the memory below vsrc into the memory below vdst in the first branch. you need to add to dst and src not vdst/vsrc.

Thanks, C rather rusty :)

http://news.ycombinator.com/item?id=3214807

Ok, updated version:

    void*
    memmove(void *vdst, void *vsrc, int n)
    {
        char *dst, *src;

        dst = vdst;
        src = vsrc;
        if(vdst > vsrc) {
            dst = vdst + n;
            src = vsrc + n;
            while(n-- > 0)
                *--dst = *--src;
        }
        else if(vdst < vsrc)
            while(n-- > 0)
                *dst++ == *src++;
        return vdst;
    }

Does this solve the bugs?

There's an == for an =. Also vdst+n is an error, I believe, because sizeof *vdst has no meaning.

Here is a standard implementation I found from some code at work.

    /* memmove.c -- copy memory.                                                                                                                                    
       Copy LENGTH bytes from SOURCE to DEST.  Does not null-terminate.                                                                                             
       In the public domain.                                                                                                                                        
       By David MacKenzie <djm@gnu.ai.mit.edu>.  */                                                                                                                 
                                                                                                                                                                
    #if HAVE_CONFIG_H                                                                                                                                               
    # include <config.h>                                                                                                                                            
    #endif                                                                                                                                                          
                                                                                                                                                                    
    void *                                                                                                                                                          
    memmove (dest, source, length)                                                                                                                                  
         char *dest;                                                                                                                                                
         const char *source;                                                                                                                                        
         unsigned length;                                                                                                                                           
    {                                                                                                                                                               
      char *d0 = dest;                                                                                                                                              
      if (source < dest)                                                                                                                                            
        /* Moving from low mem to hi mem; start at end.  */                                                                                                         
        for (source += length, dest += length; length; --length)                                                                                                    
          *--dest = *--source;                                                                                                                                      
      else if (source != dest)                                                                                                                                      
        {                                                                                                                                                           
          /* Moving from hi mem to low mem; start at beginning.  */                                                                                                 
          for (; length; --length)                                                                                                                                  
            *dest++ = *source++;                                                                                                                                    
        }                                                                                                                                                           
      return (void *) d0;                                                                                                                                           
    }

I'm starting to suspect that Russ Cox is actually a team of people, all contributing under one name.

He is really just one very productive man, and his real name is Nicholas Bourbaki.

Now that a reference my dad would love :) Not sure if the regular HN folks would know of Bourbaki though

"Nicolas Bourbaki is the collective pseudonym under which a group of (mainly French) 20th-century mathematicians wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. With the goal of founding all of mathematics on set theory, the group strove for rigour and generality. Their work led to the discovery of several concepts and terminologies still discussed."

http://en.wikipedia.org/wiki/Nicolas_Bourbaki

I pulled the repository and all of the code is very well documented, and easy to read. Really a great resource for learning OS internals.

it's small enough to fit in one `ls` screen, really inciting to be read, kinda like plan9 source code.

If anyone is interested:

http://plan9.bell-labs.com/sources/plan9/sys/src/

I was under the impression that Minix was created and used for this kind of thing. Is there something about Minix that makes it unsuitable today's classrooms?

I guess it depends on what you want to use as your textbook, Tanenbaum's books or Lions' Commentary.

A suitably motivated individual might reach out to the various accredited institutions, try and track down one of the Cmpt. Sci Profs who teaches the "Intro to Operating Systems" courses, and find out A) Which Textbook they Use. B) Which training OS system they use. C) Which language they implement their OS in. (ANSI C is likely to be popular)

Or, they could be lazy, and hope that this HN thread turns out to be a representative sample of the Textbooks/Operating Systems in use.

Well, Minix has a microkernel architecture, unlike this which seems to be monolith (and probably simpler to understand).

Minix is a microkernel design, so it's of limited use in understanding how modern OSes work.

It would be fair to say current operating systems.

Microkernels have been the wave of the future for longer than some of the most popular OSes have been around, namely Windows NT (not just Windows 7, but the whole NT design), Mac OS X (NeXTStep too, for that matter), and Linux (but, admittedly, not Unix).

If I may prognosticate, stripped-down monolithic OSes running on hypervisors are the wave of the future. Look at VM/CMS for an extreme example: CMS is about as complex as MS-DOS, being a single-user single-tasking OS with no memory protection or security model. VM is the hypervisor. Together, they date to about 1968, or a little before if you include research systems.

There are a lot of parallels between VM/CMS and a microkernel with a service built specifically to host an application. They are very different beasts at their core (a microkernel is built to connect services and a hypervisor to segregate them), but they solve similar problems in sometimes similar ways.

You seem to be talking about Service Virtual Machines:

http://www.garlic.com/~lynn/2010k.html#25

A Service VM is one where an application runs directly on the 'bare metal' provided by the VM (that is, the whole point of a VM is to multiplex the hardware; it provides few or no abstractions as such). There's no guest OS as you'd think of one.

This idea also exists in exokernel designs:

http://c2.com/cgi/wiki?ExoKernel

http://pdos.csail.mit.edu/exo.html

In an exokernel, the guest OS is reduced to a library, like libc, which is (ideally) optimized for the specific application: Emacs has its own, Apache has its own, and so on. It's a half-step removed from the Service VM idea in that the applications themselves would still get to use the OS abstractions, unaware that the OS is basically gone.

http://pdos.csail.mit.edu/6.828/schedule.html

The project page gives this link to the schedule, where the lecture notes are supposed to be, but the link 404's.

Is there a working URL for these lecture notes?

http://pdos.csail.mit.edu/6.828/2011/schedule.html

Another set of excellent free OS lecture notes here: http://pages.cs.wisc.edu/~remzi/Classes/537/Fall2011/

The lectures themselves are not xv6 specific, although the projects are xv6 based.

This is unspeakably great. I'm going to have to forward this on to my old OS professor. Really wish we had this when I took that class.

I encourage you to try out the 6.828 course material, especially the labs. It's one of the best OS courses. I had taken UCLA's CS 235 which is based on similar content [1]. Learned a lot from that.

[1]: http://www.cs.ucla.edu/~kohler/class/10f-aos/

> Although the Unix v6 source may seem like an ideal introduction to operating systems engineering because of its simplicity, students doubted the relevance of an obsolete OS written in a now defunct dialect of C. In addition, students struggled to learn the details of two different architectures, the PDP-11 and x86, at the same time.

Those students were MIT students. I'd expect MIT students to not have had a problem with either of these, so I'm a bit puzzled.

Compared to the OS course I've taken in Sweden this seems to cover more, but I can't find how many credits you get from it. It is scheduled from September to end of december, but is it full time during this period or do they take other courses at the same time?

Edit: URL: http://pdos.csail.mit.edu/6.828/2011/index.html

Most students take 6.828 along with three or four other courses.

Why not XINU? It's a great little kernel; already exhaustively documented (Lions' Commentary style) along with its TCP/IP stack.

P.S. I still maintain a very HLL is ideal for presenting multi-processing/multi-tasking to students.

Comer has a new edition of "Operating System Design: The Xinu Approach" that focuses on a Linksys/Cisco router. I've not read the text officially yet, but the drafts were very interesting. Purdue CS grad students use Xinu for the OS course projects (http://www.cs.purdue.edu/homes/cs503/).

Very interesting. Thank you :-)

The info page says that xv6 was released in Fall 2006. What's new?

Address spaces based on paging rather than segments. Much clearer context switching code. File system crash recovery via logging.

And now using the HLT instruction so you don't chew CPU power unnecessarily, great for QEMU etc on laptops. I just sent you a patch.

Edit: all the user tests passed.

One thing I forgot to mention, now that the scheduler code has been changed the famous "you are not expected to understand this" comment is gone.

Yip yip yip yip yip yip yip. Good.

Reply on news.ycombinator.com