Issue 2-30, July 30, 1997

Be Engineering Insights: Synchronization In Device Drivers, Revisited

By Rico Tudor

This article continues the exploration of process synchronization in BeOS device drivers. You may want to review the first article, "Synchronization in Device Drivers," from three months ago.

That article concluded with an example of the "z" facility which coordinates multiple "producers" and "consumers." This method yields a "broadcast" form of synchronization, where each thread examines the shared data, determining whether to proceed. As an exercise for readers, I did not show the version which uses just one semaphore. One reader, Oleg, deserves honorable mention for e-mailing the correct code.

My single-semaphore version follows. It assumes greater responsibility, being able to both coordinate threads and to lock data structures. In the previous article, locking was achieved through the lock()/unlock() calls.

struct wchan {
    sem_id xsem,
           wsem;
    uint nthread;
};

void
wacquire( struct wchan *w)
{
    static spinlock sl;

    cpu_status ps = disable_interrupts( );
    acquire_spinlock( &sl);
    if (w->xsem == 0) {
        w->xsem = create_sem( 1, "excluded");
        w->wsem = create_sem( 0, "waiting");
    }
    release_spinlock( &sl);
    restore_interrupts( ps);
    acquire_sem( w->xsem);
}

void
wrelease( struct wchan *w)
{
    release_sem( w->xsem);
}


void
wsleep( struct wchan *w)
{
    ++w->nthread;
    release_sem( w->xsem);
    acquire_sem( w->wsem);
    acquire_sem( w->xsem);
}

void
wakeup( struct wchan *w)
{
    if (w->nthread) {
        release_sem_etc( w->wsem, w->nthread, 0);
        w->nthread = 0;
    }
}

A wchan struct is allocated (statically) to protect a set of data, around which multi-threaded activities occur. An example is driver data for a serial port. N serial ports would require N wchan structs.

The general idea is to acquire exclusive use of the data when you enter the driver, and relinquish it when you leave; the relevant calls are wacquire() and wrelease(). Within the driver, you may block for any reason, by calling wsleep(), whereupon you temporarily lose control of the data. After unblocking, you automatically have control of the data, but it may have changed while you were "asleep." How were you woken up? By another thread in the driver, who called wacquire() and then wakeup().

To simplify the discussion, this article is ignoring hardware interrupts entirely. Therefore, all flows-of- control are assumed to be background threads and, of course, in the kernel. As most hardware is operated with interrupts, this code would need augmentation before such use. See the previous article for details.

Here is the standard BeOS "control" entry-point for our hypothetical driver. It demonstrates the use of the "wchan" facility. Since there are no interrupts, all data producer and consumer threads must call this function. PUT_DATA is a producer command, while GET_LINE and FLUSH_ON_NULL are consumer commands. WAIT_FOR_MORE and WAIT_UNTIL_EMPTY consume nothing, but merely synchronize on some condition.

struct device {
    struct wchan  w;
    struct clist  clist;
};

status_t
dev_control( void *v, uint32 com, void *buf, size_t len)
{
    status_t    s;

    wacquire( &dp->w);
    s = control( v, com, buf, len);
    wrelease( &dp->w);
    return (s);
}

static status_t
control( void *v, uint32 com, void *buf, size_t len)
{
    struct device  *dp;
    size_t  i;

    dp = (struct device *) v;
    switch (com) {
    case GET_LINE:
        while (findchar( &dp->clist, '\n') == 0)
            if (wsleep( &dp->w) == 0)
                return (B_INTERRUPTED);
        for (i=0; i<len; ++i) {
            int c = getc( &dp->w, &dp->clist);
            if (c < 0)
                return (B_INTERRUPTED);
            ((char *)buf)[i] = c;
            if (c == '\n')
                break;
        }
        break;
    case FLUSH_ON_NULL:
        while (findchar( &dp->clist, 0) == 0)
            if (wsleep( &dp->w) == 0)
                return (B_INTERRUPTED);
        while (dp->clist.nchar)
            if (getc( &dp->w, &dp->clist) < 0)
                return (B_INTERRUPTED);
        break;
    case WAIT_FOR_MORE:
        i = dp->clist.nchar;
        while (dp->clist.nchar == i)
            if (wsleep( &dp->w) == 0)
                return (B_INTERRUPTED);
        break;
    case WAIT_UNTIL_EMPTY:
        while (dp->clist.nchar)
            if (wsleep( &dp->w) == 0)
                return (B_INTERRUPTED);
        break;
    case PUT_DATA:
        for (i=0; i<len; ++i)
            if (putc( &dp->w, &dp->clist,
                  ((uchar *)buf)[i]) < 0)
                return (B_INTERRUPTED);
    }
    return (B_OK);
}

The purpose of the driver is to pass data between user-level threads. Data is buffered with byte-wide FIFOs, using the putc() and getc() calls. As a convenience, these will block when there is no data to get, or too much data already buffered. Note the call to wakeup() whenever the FIFO changes: This serves all threads in the driver, not just those sleeping in the clist module.

struct cdata {
    struct cdata  *next;
    uchar  c;
};
struct clist {
    struct cdata  *head,
                  *tail;
    uint  nchar;
};

putc( struct wchan *w, struct clist *cl, int c)
{
    struct cdata  *d;

    while (cl->nchar >= CLISTMAX)
        if (wsleep( w) == 0)
            return (-1);
    d = (struct cdata *) malloc( sizeof *d);
    d->c = c;
    d->next = 0;
    if (cl->head)
        cl->tail->next = d;
    else
        cl->head = d;
    cl->tail = d;
    ++cl->nchar;
    wakeup( w);
    return (c);
}

getc( struct wchan *w, struct clist *cl)
{
    struct cdata  *h;
    int  c;
    while (cl->nchar == 0)
        if (wsleep( w) == 0)
            return (-1);
    h = cl->head;
    c = h->c;
    cl->head = h->next;
    free( h);
    wakeup( w);
    return (c);
}

bool
findchar( struct clist *cl, uint c)
{
    struct cdata  *d;

    for (d=cl->head; d; d=d->next)
        if (d->c == c)
            return (TRUE);
    return (FALSE);
}

Devising a more conservative protocol for wakeup() calls in the clist module would greatly improve efficiency. A larger blocking factor for malloc() would also help!

The attentive reader might have noticed that wsleep() is defined as returning void, but is used as if it returns bool. This leads us to a key topic: The failure to acquire semaphores.

The call acquire_sem() blocks until it succeeds; this is rarely the desired behavior for device drivers. The user may wish to abort an operation which is lagging or hung. Programs may want to timeout automatically, and retry. This is all possible with the acquire_sem_etc() call. When a timeout occurs, or the thread is sent a signal, the call returns without having acquired the semaphore. The driver must respond, usually by returning an immediate error.

I must admit failure myself, in being unable to work this into the above implementation of "wchan." Readers are welcome to respond.

Therefore, I must return to a BYOB (bring your own blockable) approach, as in the first article. To recap, each thread that wants to block until "something happens" will call wsleep(). A semaphore is created on the spot, and added atomically to the list of waiting threads. Later, a different thread will call wakeup(), with the usual broadcast effect. The return from wsleep() is TRUE.

However, the return may be FALSE. In this case, a signal is pending. This could have arrived during the wsleep(), or some time before. When using acquire_sem_etc(), the BeOS will not allow a thread to block, or remain blocked, with a pending signal. For the good of the driver, the error must be propagated from wsleep(), and then out of the driver. All this occurs in the following code:

struct wchan {
    sem_id  sem;
    struct wlink  *threads;
};
struct wlink {
    sem_id  sem;
    struct wlink  *next;
};

void
wacquire( struct wchan *w)
{
    static spinlock l;
    sem_id     sem;
    cpu_status ps = disable_interrupts( );
    acquire_spinlock( &l);
    unless (w->sem)
        w->sem = create_sem( 1, "excluded");
    release_spinlock( &l);
    restore_interrupts( ps);
    acquire_sem( w->sem);
}

void
wrelease( struct wchan *w)
{
    release_sem( w->sem);
}

bool
wsleep( struct wchan *w)
{
    bool  b;
    struct wlink *l = malloc( sizeof *l);
    l->sem = create_sem( 0, "waiting");
    l->next = w->threads;
    w->threads = l;
    release_sem( w->sem);
    b = acquire_sem_etc( l->sem, 1, B_CAN_INTERRUPT, 0);
    acquire_sem( w->sem);
    return (b == B_OK);
}

void
wakeup( struct wchan *w)
{
    struct wlink  *l;
    while (l = w->threads) {
        release_sem( l->sem);
        delete_sem( l->sem);
        w->threads = l->next;
        free( l);
    }
}

The dev_control() should now be fully understandable. This article has illustrated some fairly sophisticated approaches to process synchronization, which should help writers of BeOS device drivers. There are multiple ways to coordinate threads, and to prevent corruption of data structures. The approach that a driver writer adopts will depend on the service being exported, and the particulars of the hardware.


Be Engineering Insights: European Developer's Conference

By Geoff Woodcock

I wanted to give you all a synopsis of our European developer's conferences, which were held several weeks ago, and respond to some of our European developers' comments. Without further ado...

There were two sites for the conferences, one in London and one in Frankfurt. The London conference was held at Planet Hollywood and was attended by about 40 developers. There was a small theater in the back of the building operated by a nice old guy named Reg. Reg's first comment was "Hey, I'll try to help, but I don't know anything about computers." I showed him the OS and the VideoMania demo, and he was literally walking about telling his co-workers "we need to get one of those boxes!" (It's nice to know there's still some unconquered minds out there!) Time seemed short in London, and Christophe had to drag me out of the building at the end.

Computer Warehouse, a distributor of Macintosh clones, was there demonstrating a Tanzania-based clone in a dusty blue case called...the BE MACHINE! We had some problems with the keyboards, but once we cleared these up things went fine.

The Frankfurt conference was held in a community center and was attended by about 60 developers. We had more time, and when the presentations were over, people began pulling out their Zip drives and doing some coding, trading ideas and files. PIOS, a German clone maker, was there displaying a machine that will eventually be able to boot 6 different operating systems, including the BeOS.

The European developers in attendance were, on average, younger than their US counterparts. While optimistic, many were concerned about Be's direction. Many commented on things like the BeBox, GeekPort and database features of the original BeOS. They didn't so much think these were the most important features overall for the BeOS, but they definitely felt they were distinctive, and led them to investigate Be in the first place.

The European developers seemed extremely technically- oriented, even as compared to their US counterparts. They have very technical schooling and really know the BeOS. However, they didn't seem as concerned with making money from their efforts as the US developers. One of the best things that came out of the conference is that I think many of the developers left with the realization that they could commercialize their products with some effort and some help from Be Europe. To the European developers: You have an incredible resource in the Paris office! They have a huge amount of experience and they want to help you commercialize your products. Please, contact them and let them help you.

Speaking of contacting, many of the developers had questions and comments at the conference. Most of your comments I have already made known here at Be, and I have answers for many of your questions which I will begin emailing back to you this week. If you don't get a response before Boston MacWorld, send me a message at geoff@be.com.

The business stuff aside, the mood and small sizes of the conferences made for two great parties. England and Germany, both known for good beer! I'd like to thank all of you who were there for making my trip so enjoyable, and I hope to see you all again soon!


News From The Front

By William Adams

One of the measures of excellence that most software engineers are proud of utilizing is the "I stayed up this late" factor. Dude, I stayed up 'til 5am to get this nifty feature working!! I did that last night, and I proudly showed the fruits of my labors to my wife in the morning to which she responded, "Well, that's not very practical is it?" She was absolutely right, the feature I had implemented wasn't very practical, but it has sales appeal! You want a little sizzle with that steak?

Man, you wouldn't believe how many Master's Awards entries we've seen in the last hours approaching the entry deadline. Now, I've been on the vanguard of a few emerging platforms in my day, and they objections come in waves. Something new... It will never work... Oh that thing, there's no software for it... It doesn't run Windows apps...

The words are all too familiar, and all too often we in the herd blindly follow the beat of the Master drum without looking very closely at the veracity of the statements. Well, in my humble opinion, the BeOS is quickly approaching that critical mass point. We survive long enough, interesting software shows up, a cottage industry is born. I'm telling you, this software is hot! And new stuff is coming all the time.

We've got music, lights, sounds, movies, spreadsheets, mail, paint, word processing. If you ask me, I think we're beginning to look lively.

But let's not stop here. The BeDC is coming right quick, and if you're going you'll likely be able to see all this nifty stuff. We'll have a impromptu 3D contest, we're giving out machines, we're giving out disks, there will be dancing, singing, food, entertainment, and the Macintosh faithful. But before you go, have you ever considered how many infrared output devices exist in your world? I took a quick look around the office and found a keyboard, mouse, several TV and VCR controllers, and even a couple of PDA devices that do IRDA transfers.

The funny thing about infrared is that you get to sit further away from the device you are controlling. Say, in the comfort of your living room chair, or on your bed, or what have you. It's pretty easy to train an infrared receiver to recognize when signals are coming from a particular device. So here's some more info on that prototype board that we're using to do IR.

Insight Electronics
1-800-677-7716
Part: CDB8130
$200 (for two boards)
http://www.crystal.com/

This is one of those times when I say, just go out and buy this thing. What kind of a geek are you anyway? It's loads of fun, and when you figure out that you can go buy one of those infrared keyboards for about $80, you'll have no end of fun as to the evil you could do with it.

So, to recount, we have lots of software, lots of nifty video thingies, lots of MIDI thingies, bunches of game-type thingies, accelerated 3D graphics. It's beginning to smell like soup. I think when our many thousands of magazine readers get their disks, they will be eager to buy software to play on their new toy. This is where we want to be. So before you head for Boston, do just one more compile knowing that there will be thousands of end-users who will be interested in your wares real soon now.


Protecting Investors

By Jean-Louis Gassée

Almost every day, we get mail from people interested in investing in Be. This is very flattering, we very much appreciate the sentiment it reveals, but law and common sense—they sometimes agree—dictate we decline.

I can understand the interest: In the seventies, one of my colleagues at Hewlett-Packard and Data General, Bill Foster, started a company called Stratus; they made a non-stop computer system, roughly going after the same market as Tandem, a phenomenal success at the time. On the occasion of one of my trips to the East Coast, I called on Bill Foster and offered to put my savings in his company. He smiled, thanked me and declined very politely.

I was very disappointed and, for a while, considered buying a McDonald's franchise in Paris. Fortunately, your opinion may vary, that didn't happen either and I decided I still loved computers after all. A decade and a half later, I finally invested in a start-up, Be Inc., and I now have a much better perspective on the wisdom of US securities laws and the reasons for the barriers they erect between professional investors and the rest of us.

Investing early in a high-tech start-up looks enormously attractive. Compute the returns. Today, how much is $1,000 invested in the early Microsoft worth? Or Apple, or Intel, or SGI, or Oracle—the list is wonderfully long and interesting. It attests to the greatest, fastest, legal creation of wealth in the history of mankind around Sand Hill Road in Menlo Park, CA. That road is also known as VC Gulch for its high concentration of venture capital firms. How could one not want to get in at the ground floor and enjoy the ride?

Well, there are the crashes. The roadsides of VC Gulch are littered with the carcasses of failed start-ups. Early stage high-tech companies are not good places to park college education or retirement money.

Hardier individuals will object they know the risks and are willing to invest anyway: They're able and willing to put discretionary funds in play without endangering their or their family's future. In some very limited cases, the law allows individual investors to play in the same field as the pros. The restrictions are severe and involve, among other parameters, high requirements for the individual's net worth and education—and lots of paperwork. See your friendly securities attorney for details.

There is more. Early stage companies have ambitious plans, they aim high. But software or ASICs take time, the rendez-vous in orbit with some other technology may or may not happen. For a number of reasons, the company you've invested in needs more time, more money. At this stage, professional investors make a decision: They put more money in the company, or they don't.

If they do, or if new investors come in, they evaluate the "updated" opportunity offered by the company in a number of ways. If some pros decide not to put in more money, it means they see a higher risk and/or a lower reward than they like. As a consequence, the company has to offer better terms in order to make itself at least as attractive as other deals the pros could invest in. Practically, the share of the company owned by the earlier round investors shrinks to a smaller percentage, sometimes a much smaller one. This is still preferable to closing the business, so shareholders (including the founding employees) acquiesce. They see a potential in the business, they need money to actualize said potential, and they're willing to pay the price in reducing their percentage holding.

The dilution is sometimes severe enough to be called "washing out." This is not a problem for investors who stay with the play and put money in the new round. They usually conserve their percentage of the company or pretty close to it, depending upon complex sets of terms in their initial investment. New investors also try to treat employees well by issuing new options, they need their commitment.

So, assuming the company ultimately makes it, the only parties who really suffer in this process are the investors who don't play in the new round. If they are pros, washing out and being washed out is part of their everyday life. No hard feelings. They made a judgement call.

For the "small," non-professional investor, re-investing may or may not be possible; being washed out might be perceived as an unfair experience, cautionary paperwork or not. That's where securities law and common sense agree in preventing normal people from playing with, or against, the pros. Who wants to bet money and play pick-up basketball against Michael Jordan or Dennis Rodman? And, no, I have no VC names in mind as I write this.


BeDevTalk Summary

BeDevTalk is an unmonitored discussion group in which technical information is shared by Be developers and interested parties. In this column, we summarize some of the active threads, listed by their subject lines as they appear, verbatim, in the mail.

To subscribe to BeDevTalk, visit the mailing list page on our web site: http://www.be.com/aboutbe/mailinglists.html.

NEW

Subject: Think of all the fun...

An initial public interest suggestion—that all Be developers should buy the full-blown issue of the Preview Release rather than wait to get it for free—generated a lot of mail (and no objections). War stories were swapped ("...they all laughed when I sat down to my BeBox..."), and opinions on the blinking green lights exchanged (everybody seems to like them; one listener suggested that a BeBox-bezel clone to snap onto the front of the StarMax machine would be a great Christmas present).

Ingmar Krusch fairly assessed the co-worker critic situation:

When someone laughs at my box, I turn the power off, back on, boot in 15 seconds, switch to 32 Bit resolution, open up 6 [QuickTime] movies and ask if their Pentium can do equal... [Of course] If they're not blown away by this and ask for real world applications, you should start improvising.

The thread was not without its nay-sayers. Jonathan Perret (a "believer" nonetheless, he assures us), answered Mr. Krusch's question:

You got a Millennium? As soon as I switch to 32-bit, all the redraws get very slow and ugly... Then I launch 6 QuickTime movies, the hard drive seeks like mad and renders the system nearly unusable—besides the fact that the movies are no longer at 25 fps. And besides, it's not *that* impressive. NT does it fine, in case you didn't know.

After the expected rebuttal, the thread opened a can of Pentium vs. PPC. Sit back, this one will probably be with us for awhile.

Subject: suspend_thread(), resume_thread(), and recv()

An initial question about unblocking a semaphore-blocked thread turned into a wider discussion of signals after one of our readers suggested using send_signal() instead of suspend_thread(). Are signals evil, non-portable, and old-fashioned? Or are they the only way to design a modern multi-tasking kernel? Also, is there a difference between "thread safe" and "signal safe"?

THE BE LINE: Contrary to a notion developed in this thread, suspend_thread() *does* work on a semaphore-blocked thread (the thread is immediately unblocked and suspended, as described in the Be Book).

However, there *is* a bug on the resume side—if the suspend_thread() and resume_thread() calls are too close to each other, the resume is ignored.

For now, stick a greater-than-3ms snooze between the calls (this is demonstrated in the Be Book in the snooze() description, but the snooze value is a bit on the low side.)

Subject: PR tidbits

As folks received their Preview Release CDs, they pointed out some of the rough edges, disagreed with some of the interface decisions, and made some suggestions (quoting from a variety of unnamed sources):

  • Kaleidoscope: "When you resize the window to be tall enough, a slice at the bottom doesn't refresh properly."

  • "Be seems to be measuring double-click intervals from mouse-down to mouse-down, rather than (IMHO correctly) mouse-up to mouse-down."

  • "If you want the movies to play REALLY fast, here's a secret tip: Push down the Caps Lock key before starting them. " (from Jake Hamby of Be)

  • NetPositive: "Open it up, resize it only horizontally and see the dirty trail the Location TextControl leaves behind."

  • Tracker: "If you click on a file/folder name to edit it, the cursor stays in the I-beam "edit text" shape until you do it again."

Subject: Multiple Undo/Redo

How do you treat an action that occurs "in the middle" of a series of undo/redo's? Should it be added to the end of the list, or inserted at the current position? Is it possible to store the action state as a tree (for undo, yes, but redo would be ambiguous).

Also, it was suggested that Be needs a standard undo/redo key mapping. How about Alt-z/Alt-Z? Should this be user or app-settable? And where are those user interface guidelines?

This led to a discussion of the "F<n>" keys—should they be used more often? As an example, Jon Ragnarsson suggested using an F<n> key to show/hide Replicators.

Subject: B_TRANSPARENT_32_BIT in DR9?

Sander Stoks wrote in to ask about the transparent 32 bit bug—is it fixed in PR?

The thread then became a discussion of how to manage windows that contain lots of views: Should you really have to "roll your own" views (by creating and managing rectangles yourself) in order to avoid the efficiency hit of multiple views? It was suggested that while it may be lamentable that BViews tend to become very slow when you throw a few dozen into a single window, this is simply the way of the Be world...

Jon Watte:

The only alternative I can see is moving lots of stuff from the app_server into libbe.so, and have the app_server ONLY talk to BWindows, letting BViews be handled entirely on the client side. That would reduce communication, but would probably have other problems, since that's not the solution they chose.

Marco Nelissen:

You could do it the other way around... Ideally, you should be able to add your own modules to the app_server, which would then perform layout, drawing, or whatever else needs to be done fast.

Dianne Hackborn:

...there's no reason to put layout managers in the app_server: Since they typically don't interact with the user, they don't really need the capabilities of a BView; about the only app_server-related functions they need to work with are Draw(), FrameResized(), etc., and those all can be handled outside of transactions with the server, with little trouble.

So—why isn't the BView class faster? Where does the time go? Dianne Hackborn suggested that it's sunk by the amount of data that flows between the client and the server. Jon Watte says the amount of data doesn't matter—it's the communication overhead that's consumptive. So should multiple manipulations be bracketed by calls to BWindow's DisableUpdates() and ReenableUpdates() (in order to batch the commands)?

Mr. Stoks' question never did get answered.

THE BE LINE: The 32-bit transparency bug has been fixed (in PR).

Creative Commons License
Legal Notice
This work is licensed under a Creative Commons Attribution-Non commercial-No Derivative Works 3.0 License.