nephele
/
haiku-website
0
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
haiku-website/static/legacy-docs/benewsletter/Issue4-40.html

874 lines
47 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Be Newsletters - Volume 4: 1999</title><link rel="stylesheet" href="be_newsletter.css" type="text/css" media="all" /><link rel="shortcut icon" type="image/vnd.microsoft.icon" href="./images/favicon.ico" /><!--[if IE]>
<link rel="stylesheet" type="text/css" href="be_newsletter_ie.css" />
<![endif]--><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Be Newsletters" /><link rel="up" href="volume4.html" title="Volume 4: 1999" /><link rel="prev" href="Issue4-39.html" title="Issue 4-39, September 29, 1999" /><link rel="next" href="Issue4-41.html" title="Issue 4-41, October 13, 1999" /></head><body><div id="header"><div id="headerT"><div id="headerTL"><a accesskey="p" href="Issue4-39.html" title="Issue 4-39, September 29, 1999"><img src="./images/navigation/prev.png" alt="Prev" /></a> <a accesskey="u" href="volume4.html" title="Volume 4: 1999"><img src="./images/navigation/up.png" alt="Up" /></a> <a accesskey="n" href="Issue4-41.html" title="Issue 4-41, October 13, 1999"><img src="./images/navigation/next.png" alt="Next" /></a></div><div id="headerTR"><div id="navigpeople"><a href="http://www.haiku-os.org"><img src="./images/People_24.png" alt="haiku-os.org" title="Visit The Haiku Website" /></a></div><div class="navighome" title="Home"><a accesskey="h" href="index.html"><img src="./images/navigation/home.png" alt="Home" /></a></div><div class="navigboxed" id="naviglang" title="English">en</div></div><div id="headerTC">Be Newsletters - Volume 4: 1999</div></div><div id="headerB">Prev: <a href="Issue4-39.html">Issue 4-39, September 29, 1999</a>  Up: <a href="volume4.html">Volume 4: 1999</a>  Next: <a href="Issue4-41.html">Issue 4-41, October 13, 1999</a></div><hr /></div><div class="article"><div xmlns="" xmlns:d="http://docbook.org/ns/docbook" class="titlepage"><div><div xmlns:d="http://docbook.org/ns/docbook"><h2 xmlns="http://www.w3.org/1999/xhtml" class="title"><a id="Issue4-40"></a>Issue 4-40, October 6, 1999</h2></div></div></div><div class="sect1"><div xmlns="" xmlns:d="http://docbook.org/ns/docbook" class="titlepage"><div><div xmlns:d="http://docbook.org/ns/docbook"><h2 xmlns="http://www.w3.org/1999/xhtml" class="title"><a id="Engineering4-40"></a>Be Engineering Insights: A Tutorial Introduction to CVS</h2></div><div xmlns:d="http://docbook.org/ns/docbook"><span xmlns="http://www.w3.org/1999/xhtml" class="author">By <span class="firstname">Fred</span> <span class="surname">Fish</span></span></div></div></div><p>
CVS stands for Concurrent Versions System. CVS stores different versions
of files, both individually and collectively, and allows you access to
previous versions.
</p><p>
The system is "concurrent" because it allows multiple developers to work
concurrently on the same set of files with minimal conflicts, and handle
most merging issues automatically. We won't explore merging in this
introduction; instead we'll concentrate on how a single developer can
effectively use CVS to manage a software project's source code and
related files.
</p><p>
The CVS documentation in Postscript and HTML forms, the CVS source code,
and executables for x86 and PPC BeOS 4.5.2 are available at
</p><p>
&lt;ftp://ftp.be.com/pub/experimental/tools/cvs-1.10.7-doc.zip&gt;<br />
&lt;ftp://ftp.be.com/pub/experimental/tools/cvs-1.10.7-src.zip&gt;<br />
&lt;ftp://ftp.be.com/pub/experimental/tools/cvs-1.10.7-x86.zip&gt;<br />
&lt;ftp://ftp.be.com/pub/experimental/tools/cvs-1.10.7-ppc.zip&gt;
</p><p>
To install, unzip the desired binary archive and move the CVS binary to
/boot/home/config/bin/cvs or some other suitable location in your search
path.
</p><p>
Before you can start using CVS for managing the source to your project,
you have to decide where to store the CVS repository on your system, set
up the CVSROOT environment variable that tells CVS where the repository
is, and initialize the repository.
</p><p>
You can put the repository anywhere on your system; it's useful to make a
symbolic link to the location you choose, and then always refer to the
repository via that link. This lets you move the repository around
without changing the path you use to access it. If you move it, just
update the symbolic link. To pick a root directory for the repository and
set up the symbolic link:
</p><pre class="screen">
$ mkdir -p /spare/junk/repository
$ ln -s /spare/junk/repository /boot/home/repository
</pre><p>
When you run CVS, it needs to know how to find the repository. There are
several ways to do this, including using the path to the repository you
specify via the -d option, but it's probably easiest to just set the
<code class="envar">CVSROOT</code> environment variable:
</p><pre class="screen">
$ export CVSROOT=/boot/home/repository
(hint: put this in your /boot/home/.profile)
</pre><p>
Before CVS can store anything in the repository you have to initialize it
-- with the <code class="command">cvs init</code> command:
</p><pre class="screen">
$ cvs init
$ ls -lL /boot/home/repository
total 2
drwxrwxr-x 1 fnf users 2048 Oct 2 11:00 CVSROOT/
</pre><p>
The init command has created a directory called
<code class="filename">CVSROOT</code> in the
repository, which contains a number of administration files. One of the
most useful is the "modules" file, which we won't use in this
introduction, but which you may want to read about in the CVS
documentation. It's particularly useful when you have a number of
projects to maintain.
</p><p>
Now you can start using the repository. For this example, we'll use the
<span class="application">Magnify</span> app from the sample code directory on the BeOS R4.5 CD, which you
copied to your hard drive if you installed the optional items:
</p><p>
(Note long line broken up using \ escaped newlines)
</p><pre class="screen">
$ cd /r4.5/optional/sample-code/application kit/Magnify
$ cvs import -ko -I\! \
-m "Baseline version from BeOS 4.5 CD" \
Magnify be Magnify-4 5-1
N Magnify/LICENSE
...
N Magnify/makefile
No conflicts created by this import
</pre><p>
The import command causes CVS to add this project to the repository. You
can peek at the repository to check this:
</p><pre class="screen">
$ ls -lL /boot/home/repository
total 4
drwxrwxr-x 1 fnf users 2048 Oct 2 11:00 CVSROOT/
drwxrwxr-x 1 fnf users 2048 Oct 3 11:28 Magnify/
</pre><p>
Let's examine the import command arguments
in greater detail. The -ko
option tells CVS that you don't want any keyword expansions on the file
contents. Consult the CVS docs for more detail on keywords.
</p><p>
The -I\! option tells CVS to add every file in the project, regardless
of whether or not it might be one that CVS would normally ignore, such as
object files or backup files.
</p><p>
The -m option provides a log message. If you don't supply a log message
via -m , CVS will fire up whatever editor you specified with your
<code class="envar">EDITOR</code> environment variable, and let you enter something longer than
what can be conveniently typed on the command line.
</p><p>
The Magnify arg gives the subdirectory name in the repository where the
files will be stored. The be arg is the tag used for the branch where
the files are imported. The Magnify-4 5-1 arg is the symbolic tag for
the specific set of files that correspond to this import. Note that the
'.' character is not legal in tag names, so you have to use another
character, like ' '.
</p><p>
Now that the files are in the repository, you can check out a working set
in which you can make changes. You can check out as many copies as you
wish; in fact it's often useful to have several different copies of the
sources checked out at the same time. You might have one set of sources
where you're doing active development, another set where you're fixing
bugs reported by users, etc. Every working set of sources is independent
and the changes you make will not appear in the repository or any other
copy until you commit them to the repository and update your other copies.
</p><p>
Let's take an example that shows how to check out multiple copies of the
sources, make changes in each copy, commit changes back to the
repository, and automatically merge those changes into all the copies
you've checked out. First, check out two complete sets of the sources,
one for bug fixing and one for development:
</p><pre class="screen">
$ mkdir -p /boot/home/bugfixing /boot/home/development
$ cd /boot/home/bugfixing
$ cvs checkout Magnify
cvs checkout: Updating Magnify
U Magnify/LICENSE
...
U Magnify/makefile
$ cd /boot/home/development
$ cvs checkout Magnify
cvs checkout: Updating Magnify
U Magnify/LICENSE
...
U Magnify/makefile
</pre><p>
Let's now suppose that a user complains that you don't use "rgb"
consistently in the help message; i.e., sometimes it's "RGB" and
sometimes it's "rgb." He thinks it should always be in caps since it's an
abbreviation, and you agree. Go to your checked out copy of the sources
for bug fixing, edit the file, make the change, rebuild the app, test it,
and then commit this change to the repository:
</p><p>
(Note: example lines chopped short for newsletter)
</p><pre class="screen">
$ cd /boot/home/bugfixing/Magnify
$ emacs main.cpp
$ make
gcc -c main.cpp -I./ -I- -O3 -Wall -Wno-multichar ...
gcc -o obj.x86/Magnify obj.x86/main.o -Xlinker ...
xres -o obj.x86/Magnify Magnify.rsrc
mimeset -f obj.x86/Magnify
$ obj.x86/Magnify
$ cvs diff main.cpp
Index: main.cpp
==========================================================
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.1.1.1
diff -r1.1.1.1 main.cpp
756c756
&lt; text-&gt;Insert(" which pixel's rgb values will
---
&gt; text-&gt;Insert(" which pixel's RGB values will
776c776
&lt; text-&gt;Insert(" arrow keys - move the current sele
---
&gt; text-&gt;Insert(" arrow keys - move the current sele
$ cvs commit -m "Fix inconsistent use of RGB in help"
cvs commit: Examining .
Checking in main.cpp;
/boot/home/repository/Magnify/main.cpp,v &lt;-- main.cpp
new revision: 1.2; previous revision: 1.1
done
</pre><p>
Prior to checking the changes into the repository you used the CVS diff
command to print the differences between what's currently in the
repository and what's in your working sources, just to double check what
you were about to commit to the repository.
</p><p>
In order to make it easy to check out a copy of your sources (the latest
released version), plus this bug fix, give this new set of sources the
symbolic tag "Magnify-4 5-2", to signify that it is the second revision
of the Magnify sources from 4.5:
</p><pre class="screen">
$ cvs tag Magnify-4 5-2
cvs tag: Tagging .
T LICENSE
...
T makefile
</pre><p>
At any point in the future, you can use that symbolic tag with the CVS
checkout command to recover the sources to this revision of the project:
</p><pre class="screen">
$ cd /tmp
$ cvs checkout -r Magnify-4 5-2 Magnify
cvs checkout: Updating Magnify
U Magnify/LICENSE
...
U Magnify/makefile
$ rm -rf Magnify
</pre><p>
The bug fix is now in your checked out working set for fixing bugs and
the copy in the repository, but NOT in the copy where you're doing active
development. Let's pretend that this is a critical bug fix that you also
need in your ongoing development sources. Without a source management
system like CVS, you'd have to make the same change in your development
sources and any other copies you were maintaining manually. With CVS,
it's trivial to bring all other copies up to date with no manual work.
You just use the CVS "update" command:
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ cvs update
cvs update: Updating .
U main.cpp
</pre><p>
If you make a change in one working set that conflicts with a change made
in another working set, when you update, instead of getting a line like
</p><pre class="screen">
U main.cpp
</pre><p>
you'll get
</p><pre class="screen">
M main.cpp
</pre><p>
This means that you had a "merge conflict." The <code class="filename">main.cpp</code> file now
contains fragments that look something like this:
</p><pre class="screen">
&lt;&lt;&lt;&lt;&lt;&lt;&lt;
extern int MyFunc (int a, long b);
=======
extern int MyFunc (unsigned int a, unsigned long b);
&gt;&gt;&gt;&gt;&gt;&gt;&gt;
</pre><p>
You need to examine these fragments, decide how to resolve the conflict,
and edit the file appropriately. When you check it in, if what you kept
was different from what was in the repository, the repository copy will
be updated.
</p><p>
This is a good time to mention the CVS log command, which will print a
summary of previous revisions of your files:
</p><pre class="screen">
$ cvs log main.cpp
RCS file: /boot/home/repository/Magnify/main.cpp,v
Working file: main.cpp
head: 1.2
branch:
locks: strict
access list:
symbolic names:
Magnify-4 5-2: 1.2
Magnify-4 5-1: 1.1.1.1
be: 1.1.1
keyword substitution: o
total revisions: 3; selected revisions: 3
description:
----------------------------
revision 1.2
date: 1999/10/03 17:53:26; author: fnf; state: Exp;
lines: +2 -2
Fix inconsistent use of RGB in help
----------------------------
revision 1.1
date: 1999/10/02 18:18:07; author: fnf; state: Exp;
branches: 1.1.1;
Initial revision
----------------------------
revision 1.1.1.1
date: 1999/10/02 18:18:07; author: fnf; state: Exp;
lines: +0 -0
Baseline version from BeOS 4.5 CD
==========================================================
</pre><p>
This output gives you a huge amount of useful information about the file
and its history. From it, you know that the current version of the file
(as numbered by CVS) is 1.2. You know that there are some symbolic names
like Magnify-4 5-1 and Magnify-4 5-2 that you can use to specify specific
revisions of the file, and you see what file revisions correspond to
particular changes to the file, such as that revision 1.2 fixed the
inconsistent use of RGB in the help text.
</p><p>
If you're curious about seeing the differences between revisions, you can
use the -r" option to the CVS
"diff" command to view the differences
between two revisions:
</p><p>
(Note: example lines chopped at 60 chars for newsletter)
</p><pre class="screen">
$ cvs diff -r 1.1 -r 1.2 main.cpp
Index: main.cpp
==========================================================
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.1
retrieving revision 1.2
diff -r1.1 -r1.2
756c756
&lt; text-&gt;Insert(" which pixel's rgb values will
---
&gt; text-&gt;Insert(" which pixel's RGB values will
776c776
&lt; text-&gt;Insert(" arrow keys - move the current sele
---
&gt; text-&gt;Insert(" arrow keys - move the current sele
</pre><p>
Other options are also useful in the CVS diff command, like -c to get
contextual diffs or "-p" to get the name of the function included in the
diffs.
</p><p>
Let's now go back to your development sources, and make a change that you
want to show up in future versions. Since this is only an example, we'll
use a simple change that doesn't really change the program behavior:
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ emacs main.cpp
$ cvs diff main.cpp
Index: main.cpp
==========================================================
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.2
diff -r1.2 main.cpp
3,6c3,4
&lt; /*
&lt; Copyright 1999, Be Incorporated. All Rights ...
&lt; This file may be used under the terms of the Be ..
&lt; */
---
&gt; // Copyright 1999, Be Incorporated. All Rights ...
&gt; // This file may be used under the terms of the Be ...
$ cvs commit -m "Use C++ style comments" main.cpp
Checking in main.cpp;
/boot/home/repository/Magnify/main.cpp,v &lt;-- main.cpp
new revision: 1.3; previous revision: 1.2
done
</pre><p>
The problem you now have is that you want to start a new release cycle
for your product, based on the current development sources, and only make
changes to the source for that release that are related to fixing bugs
found by beta testers. On the other hand, you have some ideas for fairly
extensive changes that will improve the product, but may destabilize the
sources for several weeks.
</p><p>
Up to this point, you have a single thread of development in the sources.
You started off with an initial revision, made a change to fix a bug,
made another change that normally would be enough to warrant releasing a
beta test copy, and presumably are going to make some additional changes
for ongoing development.
</p><p>
CVS handles this problem by letting you create a "branch" for the
release. If you think of the sequence of revisions of a file as a tree,
you might get something like the following tree (knocked over by a
hurricane):
</p><pre class="screen">
(beta 2.0) (rel 2.0) (rel 2.1)
O-------O-----------O-----------O
Release 2 branch) /1.3.1 1.3.2 1.3.3 1.3.4
/
root / 1.4 1.5 1.6
O----- O------O-------O----------O---------O----&gt; trunk
1.1 1.2 1.3 \
O------&gt;
1.4.1
(Release 3 branch)
</pre><p>
By creating a branch, you can continue development on the main trunk,
without destabilizing the sources on the branch. Ultimately the branch
will terminate in a release, perhaps followed by a bug fix release or
two, and then stop growing.
</p><p>
When creating a branch, it's useful to first mark the branch point with a
symbolic tag, so that you always have an easy reference to the point in
the sources where the branch was made. You do this with the CVS "tag"
command:
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ cvs update
cvs update: Updating .
$ cvs tag release2-branchpoint
cvs tag: Tagging .
T LICENSE
...
T makefile
</pre><p>
To create the actual branch in the repository, you use the tag command
again, but this time with the -b option. You give the branch the
symbolic tag "release2-branch", and from now you can refer to the branch
itself using that symbolic name.
</p><pre class="screen">
$ cvs tag -b release2-branch
cvs tag: Tagging .
T LICENSE
...
T makefile
</pre><p>
Note that the branchpoint tag (release2-branchpoint) refers to a very
specific set of sources that will never change, while in most situations
the branch tag (release2-branch) refers to whatever set of sources are
the current head of the branch.
</p><p>
Now you need to check out a working set of sources for the branch
development, build a release, and send it out to beta testers:
</p><pre class="screen">
$ mkdir -p /boot/home/releases
$ cd /boot/home/releases
$ cvs -q co -r release2-branch Magnify
U Magnify/LICENSE
...
U Magnify/makefile
$ mv Magnify Magnify-release2
$ cd Magnify-release2
$ make
...
(ship copy to beta testers)
</pre><p>
Now you return to your ongoing development sources. You make a bunch of
changes that result in your development sources failing to build, and
while you're trying to figure the problem out, you get your first bug
report from the beta testers (they're pretty d**n quick):
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ make
gcc -c main.cpp -I./ -I- -O3 -Wall -Wno-multichar ...
/boot/home/development/Magnify/main.cpp:52: syntax error
$ (you have mail)
</pre><p>
You switch back to the release sources, poke around in them, and quickly
spot the problem. You install a fix, commit it to the repository, tag the
new sources as "release2-beta2", create a new beta release and send it
out:
</p><pre class="screen">
$ cd /boot/home/releases/Magnify-release2
$ emacs main.cpp
$ cvs commit -m "Fix problem reported by beta1 testers"
cvs commit: Examining .
Checking in main.cpp;
/boot/home/repository/Magnify/main.cpp,v &lt;-- main.cpp
new revision: 1.3.2.1; previous revision: 1.3
done
$ cvs tag release2-beta2
cvs tag: Tagging .
T LICENSE
...
T makefile
$ make
...
(ship beta2 copy to beta testers)
</pre><p>
Since branches are independent threads of development, if you want the
fix made on the release 2 branch to migrate back to the trunk, which you
almost certainly do in most cases, you have to do what is known as a CVS
"join." This is where the branchpoint tag comes in handy. You know that
you tagged the sources with the branchpoint tag, fixed a bug, and tagged
them again with "release2-beta". So you can migrate the patch back to the
trunk with like this:
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ cvs -q update -j release2-branchpoint -j release2-beta2
M main.cpp
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.3
retrieving revision 1.3.2.1
Merging differences between 1.3 and 1.3.2.1 into main.cpp
</pre><p>
The main.cpp file in your working set for the development trunk now
contains the patch you made on the release branch, as well as all the
other changes you made that are not yet checked in. When you check those
in, the release patch is checked into the trunk as well. The only danger
is that if you blow away the changes you're working on, you will have
also blown away the bug fix you made in the release branch, and it won't
make it back to the trunk.
</p><p>
A better way to handle the migration of the patch from the release branch
to the trunk is to create a temporary working set that is the latest set
checked into the trunk of the repository, run the join command to migrate
the patch to the trunk sources, and commit the patch back to the trunk:
</p><pre class="screen">
$ cd /tmp
$ cvs -q checkout Magnify
U Magnify/LICENSE
...
U Magnify/makefile
$ cvs -q update -j release2-branchpoint -j release2-beta2
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.3
retrieving revision 1.3.2.1
Merging differences between 1.3 and 1.3.2.1 into main.cpp
$ cvs commit -m "Merge bugfix from release 2 to trunk"
cvs commit: Examining Magnify
Checking in Magnify/main.cpp;
/boot/home/repository/Magnify/main.cpp,v &lt;-- main.cpp
new revision: 1.4; previous revision: 1.3
done
$ rm -rf Magnify
</pre><p>
Note how easy it is to create a temporary sandbox to make a quick change
and then blow it away when you're done with it. This is partly because
CVS does not maintain any state information in the repository about what
files you have checked out or where they live.
</p><p>
Now, if you switch back to your development sources and do a CVS update,
CVS notices that the patch from the release branch is already in your
working sources (as a result of running the join command earlier) and
updates you to the latest revision of the file plus your uncommitted
local changes:
</p><pre class="screen">
$ cd /boot/home/development/Magnify
$ cvs -q update
RCS file: /boot/home/repository/Magnify/main.cpp,v
retrieving revision 1.3
retrieving revision 1.4
Merging differences between 1.3 and 1.4 into main.cpp
main.cpp already contains the diffs between 1.3 and 1.4
</pre><p>
Of course, local development modifications that you haven't checked yet
in are unaffected, as you see when you run <code class="command">make</code> again:
</p><pre class="screen">
$ make
gcc -c main.cpp -I./ -I- -O3 -Wall -Wno-multichar ...
/boot/home/development/Magnify/main.cpp:53: syntax error
...
</pre><p>
Some other useful commands are
</p><pre class="screen">
cvs add - add a new file to the repository
cvs remove - remove a file from the repository
cvs tag name - give current sources symbolic tag "name"
cvs rdiff - examine differences between versions
</pre><p>
Some additional hints. Use your repository to checkpoint your work
occasionally, at points where you've reached some sort of milestone. By
checking the latest changes into the repository, you ensure that you
don't lose your work, or can revert back to a previous checkpoint if some
development path turns out to be a dead end.
</p><p>
Make liberal use of symbolic tags. Think of a tag as a handle for
grabbing a specific set of sources regardless of their individual version
numbers. Give the tags meaningful names.
</p><p>
Back up your repository frequently. If you lose it, you lose a lot more
than just your current development sources!
</p><p>
DISCLAIMER: CVS is unsupported software. There is no warranty that it is
suitable for any particular purpose. Neither the author nor Be Inc. is
liable for any loss of data that may occur as a result of using this
software.
</p></div><hr class="pagebreak" /><div class="sect1"><div xmlns="" xmlns:d="http://docbook.org/ns/docbook" class="titlepage"><div><div xmlns:d="http://docbook.org/ns/docbook"><h2 xmlns="http://www.w3.org/1999/xhtml" class="title"><a id="DevWorkshop4-40"></a>Developers' Workshop: Condition Variables, Part 2</h2></div><div xmlns:d="http://docbook.org/ns/docbook"><span xmlns="http://www.w3.org/1999/xhtml" class="author">By <span class="firstname">Christopher</span> <span class="surname">Tate</span></span></div></div></div><p>
Last week I presented a condition variable (or "CV") implementation for
BeOS. If you've looked over the code, you may have found it rather
convoluted. I agree, but the complexity is not without reason. CVs are
low-level atomic scheduling primitives, and expressing them in terms of a
different primitive, the semaphore, is decidedly nontrivial. The
complexity is increased by the restriction that the CV operations be
implemented as a set of user-level functions, with no changes to the
kernel. In this article I'll explain why the CV implementation is so
involved, by illustrating a bit of the design process that went into its
creation.
</p><p>
First things first. The source is available on the Be FTP site at this
URL:
</p><p>
&lt;ftp://ftp.be.com/pub/samples/portability/condvar.zip&gt;
</p><p>
Fundamentally, CVs have two operations, waiting and signalling. Waiting
is a blocking operation, and in BeOS the only blocking primitive is the
semaphore, so a CV "wait" needs to be implemented as a semaphore
acquisition. That, in turn, dictates that the "signal" operation be a
semaphore release. Add to this the standard behavior that waiting on a CV
unlocks then relocks an external mutex and we see that these two
operations will look something like this (in pseudo-C):
</p><pre class="programlisting c">
<code class="function">cond_wait</code>(<span class="type">condvar_t*</span> <code class="parameter">cv</code>, <span class="type">mutex_t*</span> <code class="parameter">mutex</code>)
{
<code class="function">unlock</code>(<code class="parameter">mutex</code>);
<code class="function">acquire_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">semaphore</code>);
<code class="function">lock</code>(<code class="parameter">mutex</code>);
}
<code class="function">cond_signal</code>(<span class="type">condvar_t*</span> <code class="parameter">cv</code>)
{
<code class="function">release_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">semaphore</code>);
}
</pre><p>
Ideally, this would be a sufficient. Unfortunately, there are a couple of
problems. First, signalling releases the underlying semaphore even when
there are no waiters. This means that threads attempting to wait later on
will experience immediate, spurious wakeups until they exhaust the
semaphore's accumulated "extra" signals. This is unfortunate, but it's
technically allowed by the POSIX condition variable standard: spurious
wakeups are deemed an acceptable price for efficient CVs.
</p><p>
There's a worse problem, however: the mutex unlock and semaphore
acquisition are not atomic. The waiting thread could be rescheduled
between those two operations, and this can lead to incorrect behavior in
some situations. Here's one example: imagine two threads running the
following loops endlessly:
</p><pre class="programlisting c">
<span class="type">mutex_t*</span> <code class="varname">mutex</code> = <code class="constant">MUTEX_INITIALIZER</code>;
<span class="type">condvar_t*</span> <code class="varname">cv</code> = <code class="constant">COND_INITIALIZER</code>;
<span class="type">volatile int</span> mode = 0;
thread A:
{
<code class="function">lock</code>(<code class="varname">mutex</code>);
for ( ; ; <code class="varname">mode</code> = 0, <code class="function">cond_signal</code>(<code class="varname">cv</code>) )
{
while (<code class="varname">mode</code> == 0) {
<code class="function">cond_wait</code>(<code class="varname">cv</code>, <code class="varname">mutex</code>); <span class="comment">// line A</span>
}
}
}
thread B:
while (<code class="constant">true</code>) {
<code class="function">lock</code>(<code class="varname">mutex</code>); <span class="comment">// line B</span>
if (<code class="varname">mode</code> == 0) {
<code class="varname">mode</code> = 1;
<code class="function">cond_signal</code>(<code class="varname">cv</code>); <span class="comment">// line C</span>
}
while (<code class="varname">mode</code> != 0) {
<code class="function">cond_wait</code>(<code class="varname">cv</code>, <code class="varname">mutex</code>); <span class="comment">// line D</span>
}
<code class="function">mutex_unlock</code>(<code class="varname">mutex</code>);
}
</pre><p>
These two threads ping-pong back and forth, using the CV as a signal to
do so. Now, imagine that thread A is calling <code class="function">cond_wait()</code> in line "A". The
mutex is unlocked inside the <code class="function">cond_wait()</code> implementation, but let's assume
that thread A is preempted after the unlock but before it acquires the
semaphore, and thread B begins running. Thread B acquires the
now-available lock in line "B", sees that mode == 0, sets mode = 1, and
calls <code class="function">cond_signal()</code> in line "C".
This releases the <code class="varname">cv</code> semaphore, making
it available. Thread B then calls <code class="function">cond_wait()</code> in line "D", which releases
the lock and acquires the underlying semaphore—successfully! This is a
spurious wakeup, which is allowed, so thread B has to re-test the
condition that it's waiting on. "mode" is still non-zero, so thread B
repeats the call to <code class="function">cond_wait()</code> at line "D", this time blocking on the cv
semaphore. Now thread A finally gets another chance to run, picking up
where it left off in the middle of the <code class="function">cond_wait()</code> implementation: it
also attempts to acquire the CV's semaphore, and blocks. Deadlock: both
threads are blocked on the same semaphore.
</p><p>
This example isn't contrived. This exact deadlock occurred in real code
-- known to work properly on other platforms—when the developers used
a BeOS condition variable implementation that turned out to be overly
simplistic.
</p><p>
So, we need a mechanism to make the unlock-and-block *look* atomic. More
precisely, we need to prevent a signal-then-wait sequence from racing
ahead of some other thread which has begun the wait process but not yet
blocked on the CV's semaphore. To do this, we'll need some mechanism that
forces signallers to defer to waiters, even if the waiters haven't yet
blocked on the semaphore. The mechanism I chose was to use an additional
semaphore for "handshaking." The signaller waits for the in-progress
waiter by blocking on the handshake semaphore, which the waiter releases
upon awakening, i.e., receiving the signal.
</p><p>
This introduces a new complexity, however: the signaller has to know,
when releasing the main semaphore, whether or not there's a waiter to
answer the handshake. Testing the CV semaphore's count isn't sufficient;
recall that the very problem we're trying to solve involves a waiter that
hasn't yet acquired that semaphore. So, we need more bookkeeping: the
waiting thread has to inform the signaller, somehow, of its presence.
</p><p>
To accomplish this, and properly account for the cases when multiple
threads are trying to wait simultaneously, we add a count to the
<span class="type">condvar_t</span> structure, called <code class="varname">nw</code> for
"number of waiters." Threads increment the
count in <code class="function">cond_wait()</code>, before they unlock the mutex, then decrement it
again once they awaken, after they handshake with their signaller. The
signaller uses this count to determine whether a handshake is necessary.
Of course, the count manipulations need to be atomic, otherwise
simultaneous waiters will corrupt the count.
</p><p>
The implementation now looks like this:
</p><pre class="programlisting c">
<code class="function">cond_wait</code>(<span class="type">condvar_t*</span> <code class="parameter">cv</code>, <span class="type">mutex_t*</span> <code class="parameter">mutex</code>)
{
<code class="function">atomic_add</code>(&amp;<code class="parameter">cv</code>-&gt;<code class="varname">nw</code>, 1);
<code class="function">unlock</code>(<code class="parameter">mutex</code>);
<code class="function">acquire_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">semaphore</code>); <span class="comment">// line E</span>
<code class="function">atomic_add</code>(&amp;<code class="parameter">cv</code>-&gt;<code class="varname">nw</code>, -1); <span class="comment">// line F</span>
<code class="function">release_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">handshake</code>);
<code class="function">lock</code>(<code class="varname">mutex</code>);
}
<code class="function">cond_signal</code>(<span class="type">condvar_t*</span> <code class="parameter">cv</code>)
{
<span class="type">int</span> <code class="varname">count</code> = <code class="parameter">cv</code>-&gt;<code class="varname">nw</code>;
if (<code class="varname">count</code> &gt; 0)
{
<code class="function">release_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">semaphore</code>);
<code class="function">acquire_sem</code>(<code class="parameter">cv</code>-&gt;<code class="varname">handshake</code>); <span class="comment">// defer to waiter</span>
}
}
</pre><p>
This is better in two ways. First, it avoids the race condition
illustrated above; the signaller defers to the awakened thread for a
handshake, at which point both the wait and the signal have "completed,"
and the CV is back to a neutral state. Second, this new implementation
doesn't release the primary semaphore unless there's actually a waiter
present, which avoids the spurious wakeups of the initial approach.
</p><p>
Unfortunately, this implementation is still insufficient. There is
another dangerous race condition: calls to <code class="function">cond_signal()</code> might occur
between lines "E" and "F" above; that is, after the waiter awakens but
before the count is adjusted. These post-wakeup <code class="function">cond_signal()</code> invocations
would still see the waiter count as non-zero, so they would still release
the main semaphore and try to handshake with the (nonexistent) waiter,
and hang in <code class="function">cond_signal()</code>.
</p><p>
There's also a situation that arises because <code class="function">cond_signal()</code> is not really
the only way that a waiter can be awakened. It's possible that some other
thread posted an interrupt to the waiting thread via <code class="function">kill()</code> or a similar
function; that would interrupt the waiter's attempt to acquire the main
semaphore. We'd like to behave properly in such a case, with the
<code class="function">cond_wait()</code> returning <code class="constant">B_INTERRUPTED</code>
but without attempting to handshake with a
signaller. Similarly, the POSIX standard also mandates a function called
<code class="function">cond_timedwait()</code>, which allows a thread to wait until a specified
absolute time for the CV to be signalled, at which point the wait times
out and returns a suitable error code. In both of these cases, the
awakened thread must be able to discern whether there are any signallers
with which to handshake.
</p><p>
The multiple-signaller race issue is addressed by adding another lock to
the <span class="type">condvar_t</span> structure in order to serialize the <code class="function">cond_signal()</code>
operation, forcing the racing signallers to wait patiently for ongoing
signal-and-handshake sequences to complete. The aborted-wait issue, in
turn, requires that waiters have some knowledge of whether there are
signallers in progress in order to handshake when expected to. This is
accomplished by adding a signals-in-progress count to the <span class="type">condvar_t</span>
structure. We'll call the new lock "signalLock," and the new count "ns"
for "number of signals." Here's the final implementation:
</p><pre class="programlisting c">
<code class="function">cond_wait</code>(<span class="type">condvar_t*</span> <code class="parameter">condvar</code>, <span class="type">mutex_t*</span> <code class="parameter">mutex</code>)
{
<span class="type">status_t</span> <code class="varname">err</code>;
<code class="function">lock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
<code class="parameter">condvar</code>-&gt;<code class="varname">nw</code> += 1;
<code class="function">release_sem</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
<code class="function">unlock</code>(<code class="parameter">mutex</code>);
<code class="varname">err</code> = <code class="function">acquire_sem</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">semaphore</code>);
<code class="function">lock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
if (<code class="parameter">condvar</code>-&gt;<code class="varname">ns</code> &gt; 0)
{
<code class="function">release_sem</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">handshakeSem</code>);
<code class="parameter">condvar</code>-&gt;<code class="varname">ns</code> -= 1;
}
<code class="parameter">condvar</code>-&gt;<code class="varname">nw</code> -= 1;
<code class="function">unlock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
<code class="function">lock</code>(<code class="parameter">mutex</code>);
return <code class="varname">err</code>;
}
<code class="function">cond_signal</code>(<span class="type">condvar_t*</span> <code class="parameter">condvar</code>)
{
<span class="type">status_t</span> <code class="varname">err</code> = <code class="constant">B_OK</code>;
<code class="function">lock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
if (<code class="parameter">condvar</code>-&gt;<code class="varname">nw</code> &gt; <code class="parameter">condvar</code>-&gt;<code class="varname">ns</code>)
{
<code class="parameter">condvar</code>-&gt;<code class="varname">ns</code> += 1;
<code class="function">release_sem</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">semaphore</code>);
<code class="function">unlock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
<code class="function">acquire_sem</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">handshakeSem</code>);
}
else <span class="comment">// no waiters, so the signal is a no-op</span>
{
<code class="function">unlock</code>(<code class="parameter">condvar</code>-&gt;<code class="varname">signalLock</code>);
}
return <code class="varname">err</code>;
}
</pre><p>
Because a wait can be interrupted at any instant, including while a
signaller believes itself to be waking up the waiting thread, sometimes
handshakes are necessary even when threads time out. This implies that
the decision to handshake should be based solely on the signal count, not
on whether the wait timed out.
</p><p>
Access to both the signal and waiter counts is serialized through the
signalLock because both waiters and signallers use those counts to decide
whether to handshake. Conceptually, that lock allows only one thread to
formally enter a waiting or signalling state at a time, preventing the
races described earlier in this article. Because the lock provides
serialization, atomic arithmetic is unnecessary.
</p><p>
The source code for the condition variable implementation is more
complete than I've presented here; it deals with interrupts coherently,
and handles the CV "broadcast" and "timedwait" operations. The code is
commented so that you can tell what it's doing; those two operations are
simple generalizations of the basic "signal" and "wait" cases. The
biggest drawback to this implementation is its overhead: it requires an
extra pair of context switches per awakened waiter, plus it imposes
fairly strict serialization on nearly simultaneous signal and wait
operations. This is unfortunate, but it's the price we pay for having a
correct CV implementation that does not rely on any kernel support other
than sempahores.
</p></div><hr class="pagebreak" /><div class="sect1"><div xmlns="" xmlns:d="http://docbook.org/ns/docbook" class="titlepage"><div><div xmlns:d="http://docbook.org/ns/docbook"><h2 xmlns="http://www.w3.org/1999/xhtml" class="title"><a id="Gassee4-40"></a>From Socialism to Entrepreneurial Capitalism</h2></div><div xmlns:d="http://docbook.org/ns/docbook"><span xmlns="http://www.w3.org/1999/xhtml" class="author">By <span class="firstname">Jean-Louis</span> <span class="surname">Gassée</span></span></div></div></div><p>
No, this isn't about the respective merits of Old World and New World
cultures. Or about The Fatal Conceit, which sounds like a reference to
e-stock market caps but, in fact, is the name of a book by Friedrich Von
Hayek, a Nobel apostle of the free market. And that brings me to our
topic: broadband, earlier misunderstandings, and ISDN.
</p><p>
Today, we learned that Paul Allen invested 1.5 billion dollars in RCN.
Paul was a Microsoft co-founder and now is a billionaire investor. RCN is
a DSL supplier bent on becoming a dominant player in the broadband age.
The news delights me, because for about ten years, I've been an ISDN
bigot, frustrated to see such promising technology fail to get traction
in the real world.
</p><p>
The demos were terrific, especially in the days of 2400 bps modems. The
call was set up in 250ms with no 25-second (when successful) modem mating
chant. The speed was incredible; if you could combine two B channels, it
was 20 to 400 times as fast as an ordinary phone line. Any change by more
than one order of magnitude, by more than a factor of ten, is a
revolution, not an evolution (which sounds like a consultant mating song).
</p><p>
I remember bridging AppleTalk networks through an international ISDN
call, drag and drop heaven. But I was wrong. I was taken in by the demo.
It wasn't reality—ISDN was socialism. By that I mean we were at the
mercy of phone company apparatchiks; we could get a line attribution when
the state monopoly bureaucrats got around to processing the paperwork.
Actual installation was the fiefdom of another set of rulers. But it
often worked. Not always, though often enough to tease us with visions of
online bliss. But we were never admitted to heaven.
</p><p>
Now, we have entrepreneurial capitalism driving broadband into the
marketplace. By entrepreneurial capitalism, I mean large sharks on Sand
Hill Road as well as legions of smaller piranhas, all fighting for a
piece of the broadband market, for a share of the Evernet, as John Doerr
calls the next generation of the Internet. I was naive in the past, so am
I naive again about broadband? This time, I think not, because there is
competition, because we're no longer at the mercy of established phone
companies, because the Web has whetted our appetite for instant-on,
megabit-per- second connections, because we see new forms of Web
applications combining information, entertainment, and transactions.
</p><p>
Competition is organized in variations of cable modems, DSL, and wireless
cable. The last is a charming neologism, which refers to wireless two-way
connections to offices and homes offering the bandwidth of cable, or
more. All three classes have their problems. Cable modems suffer from
poor infrastructure and, some say, the cable companies' reputation for
poor service. Wireless cable isn't broadly deployed outside of high-end
applications and needs precious real estate for antennas. DSL uses the
local loop, the phone wires between my house and the central office. But
these wires aren't always up to the task—although it depends who you
ask.
</p><p>
In what the world perceives as the mecca of high-tech, in the heart of
Silicon Valley, downtown Palo Alto, not far from one of the largest
Internet nodes, the phone company says my house can't get a DSL
connection. Fortunately, new regulations force the phone company to rent
wires to competitors. One of them, recently acquired by RCN, says it
could get a DSL connection to my house. We'll see. And there are other
similar DSL stories.
</p><p>
So, yes, it's messy. But that's the good news. The glacial Old Order
wasn't much fun. We like broadband, it creates opportunities for BeOS on
both sides of the pipe. We'd rather have the messy, animated frontier
scene we see today.
</p></div></div><div id="footer"><hr /><div id="footerT">Prev: <a href="Issue4-39.html">Issue 4-39, September 29, 1999</a>  Up: <a href="volume4.html">Volume 4: 1999</a>  Next: <a href="Issue4-41.html">Issue 4-41, October 13, 1999</a> </div><div id="footerB"><div id="footerBL"><a href="Issue4-39.html" title="Issue 4-39, September 29, 1999"><img src="./images/navigation/prev.png" alt="Prev" /></a> <a href="volume4.html" title="Volume 4: 1999"><img src="./images/navigation/up.png" alt="Up" /></a> <a href="Issue4-41.html" title="Issue 4-41, October 13, 1999"><img src="./images/navigation/next.png" alt="Next" /></a></div><div id="footerBR"><div><a href="http://www.haiku-os.org"><img src="./images/People_24.png" alt="haiku-os.org" title="Visit The Haiku Website" /></a></div><div class="navighome" title="Home"><a accesskey="h" href="index.html"><img src="./images/navigation/home.png" alt="Home" /></a></div></div><div id="footerBC"><a href="http://www.access-company.com/home.html" title="ACCESS Co."><img alt="Access Company" src="./images/access_logo.png" /></a></div></div></div><div id="licenseFooter"><div id="licenseFooterBL"><a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/3.0/" title="Creative Commons License"><img alt="Creative Commons License" style="border-width:0" src="https://licensebuttons.net/l/by-nc-nd/3.0/88x31.png" /></a></div><div id="licenseFooterBR"><a href="./LegalNotice.html">Legal Notice</a></div><div id="licenseFooterBC"><span id="licenseText">This work is licensed under a
<a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/3.0/">Creative
Commons Attribution-Non commercial-No Derivative Works 3.0 License</a>.</span></div></div></body></html>
Reference in New Issue View Git Blame Copy Permalink