The Silk Road

“In Xanadu did  Kublai Khan a stately Pleasure Dome decree”  Thus did Coleridge start his epic poem about the land controlled by the Mongol Great Khan, as visited by Marco Polo.

I’d often heard while growing up that the renaissance in Europe was spurred by trade from the far east, which was, Ironically kicked off by the Crusades.

Turkey, Kurdistan, Iraq, Iran, Afghanistan, Turkmenistan, Tajikstan, China.  These are the countries of the Silk Road. I find it amazing that we are so focused on many of these countries at this point in time, when so many of them were bypassed by history for such long stretches.

We claim that there are seven continents.  There are six.  Europe and Asia are one land mass, with nothing marking the change from one to the other but a set of mountains that are not even the largest on the continent.  Don’t feel bad, Urals.  No mountain range on the planet can compete with the Himalayas. The Urals certainly were not enough of a barrier to keep the Mongols out of Europe, nor the Russians out of Siberia.   Maybe they really shouldn’tbe the dviding line between continents.

So we have Eurasia.  Let’s face it, Eurasia is the world scene.  They only really notice America when we come over there.  Yes, humanity came from Africa.  But things really got interesting when people spewed all over Asia.

the Silk road connects the cradle of wester civilization, Uruk, with the cradle of Easter Civilization, the Central Kingdon. In both cases, founded on not one but two rivers.  The tribes that migrated from Africa to China did so by this ancient silk road, or at least vaguly followed it.  I dout any tread too far north, as the equatorial nurturing of the homo-sapiens was not very likely drawn to the cold siberian heights before encountering the far more hospitable Yangtze basin.  Farm more likely that they actually came trhrough India and southeast Asia, but that still means they traversed the  majority of the silk road before meandering off down the Khyber pass.

I’ve been reading a lot about this region lately.  Right now, I am reading a book on Afghanistan, alough stricly speaking it is mostly a book on Afghanistan’s encounters with outside powers. Aghansitan is U shaped in its lowlands, looping around the southern end of the Ural Mountains.  To use a military term, the major avenues of approach are:  From the East, via the passes in the mountains from Pakistan, from the west in a corridor between the Caspian Sea and the mountains of the Iran center, and from the north basically the whole frontier is exposed to the Transoxian countries clear up to the Siberian steppes. Adfghasnistan has been invaded via all of these approaches.  Alexander the Great and later the Persians and Caliphates came from the West.  The British came up from India, twice, not a passage I would recommend.  The Mongols, the Soviets, and the America backed Wester Alliance came from the north.

The mountains in the center of the country are the Hindu Kush.  To get from Kabul, the capitol, to Mazar e Sharif , the largest city in the north, one traditionally had to cut through various passes.  The Soviets funded a highway through the mountains, along with a two mile tunnel.  That should give a sense at how hard communication must be in this place.

I have to wonder what it would have been like to be on a merchant caravan shortly after Marco Polo published his travels and the flood from the West began.  Set sail out of Venice, land somwhere in Turkey, travel across to Mesopotamia, down the Tigris and the cut over into Iran.  Skirt the Caspain sea, and by now you are in a land that vaguely remembers Greeece, and knows nothing of the west except reports of distant wars .  You keep going to a place where Islam only has a tenuous hold, and there only in the lowlands.  Do you stay north, risk the mountains and the dester to make it to distant Cathay, or go south do Hindustan where the people are even more exotic, the languages are more diverse.  Oh, and to get there, you have to travese steep moutain ravines overwatched by tribes that demand bribes at every juncture, and even then might not leave you alive.

Growing up in America, you realize how shallow our histories are.  We have no written record of the aboriginal tribes here, just scattered remains viewed through the dubious eyes of the christian missionaries.  Yes, there were greater civilizations to the south, but that is a long way from my native Massachusetts.  I am often jealous of the history clinging to the peaks and valleys of these places, places that were old when Techonctilan and Machu Pichu were young.  Idon’t envy the citizens of those realms the hardships they face either today, nor through the centuries.  I know that many of my own ancestors spent the bulk of their lives not so very far away in the  regions of Ukraine, Russia, and Polond.  I know that my Jewish heritage comes from the Jordan rivere civilizations.  I know that there must be the blood of at least a few wild horsemen from the Asiatic steppes intermingled with my semitic and Rus bloodlines.  I think it would be fascinating to be able to view the entirety of my family tree.

Questions for GRE Prep

This list of question was from a Slashdot post. Here are my answers.

Do you remember what LALR stands for?

This is a form of grammer parser. Look Ahead Left to Right. It accepts/parses Context sensitive grammers.
Can you calculate the cost of a pipeline bubble or a branch misprediction? What information would you need to do so?

You can calculate the cost of a specific misprediction under some architectures. You would need to know what the instructions to be executed in the incorrect case are, how long they take, and whether you can undo them or not. For instance in the sample code:

if     (i){   do_x();  } else{  do_y(); }

If both do_x and do_y are non, inlined functions, you know that a function call will happen.  Assume i has to fetched from memory, if  the addresses of do_x and do_y must also be fetched from memory, there is a likelihood of fetching the wrong address for the call operation.  If, on the other hand, do_y is inlined, and the compiler determines this to be the likely path, the cost will be whatever work do_y executes while waiting on the fetch of (i).

Deeper pipelines have even worse issues, as the “most likely path” may only be executed in it’s entirety a relativelyfew number of times, meaning much of the work done by deeper pipeline stages gets discarded.

How is depth-first/breadth-first related to stacks/queues related to LIFO/FIFO?

a stack is a last in first out (LIFO) data structure

a queue is a first in first out (FIFO) data structure.

In a depth first search, traversing down the the search tree is analogous to pushing values onto a stack. A depth first search is easily implemented using recursion, where the stack is the actual program stack.

In a bredth first search, you traverse across all of the children of the start node. As you search each child, you add it to a queue. Once the current node has no more children, you remove the item at the head of the queue and process it in the same manner. Continue until you meet the search criteria or there is nothing left in the queue.

What is the stack pointer?

The element of the register file that indicates where the top of the stack is for a process/thread.

What is the frame pointer?

On some architectures, a separate register points to a location on the stack that indicates where the currently executing function’s scope begins. On x86 and later architectures, there is no frame pointer register. However, the concept of frame pointer is still valid, as the return location of the current function will be pushed onto the stack with a call operation. To return from a function, this value is popped off the stack and put in the instruction register.

An interesting note is that this value may not always refer to the calling function. For example, assume you have three functions main, outer and inner. Outer and inner have identical parameter lists, for this example, a single integer value x.

void inner(int x){

}

void outer(x){

inner(x)

}

main(){

int x;

outer(x);

}

The generated assembly for main will be something like:

mov X,%ebp
call <outer>

But for main it can be

jmp <inner>

The reason is that there is no need to clean up the paramters after the call to inner. When inner completes, the return value stored on the stack will be from main, one after the call to outer. This is called a tail call and is a very common compiler optimization.

What is an interrupt?

An indication of an asynchronous event that the operating system must handle. There are two forms of interrupts, hardware and software. Examples of events which generated interrupts are: request I/O is avaialble from a device, a clock tick has occured, a user has typed a key on a keyboard. Typically, the OS handles the interrupt in two steps, a top half and a bottom half. The Top half is everything that must happen immediately, the bottom half is everything that must be done eventually. In the top half, the systems does things like recording the type of the interrupt, and scheduling the bottom half by placing it on a queue. The bottom half is what would be responsible for reading the data from the network device or linking up the key pressed to the appropriate TTY.

What are the three primary elements of OOP?

I don’t know if I would say there are three. Really, there are only two. Encapsulation and Polymorphism. Inheritance is in most forms of object oriented programming languages, but I agree with people who call this “Class Oriented Programming.” Protype based object oriented languages such as javascript may or may not be described as having inheritance. In this kind of language, a new object is created only by cloning the original object, and then modifying it. Since this is a shallow copy, it will have the same set of functions listed as methods of the object. These can be overloaded by replacing them. This is a instance of the Prototype design pattern.

Encapsulation means that you only have access to the interface of the object, not the underlying implementation. I would argue that Javascript provides no method to hide a method or property, and thus does not really encapsulate. Then again, java provides the entire introspection API, so there are often ways to get around encapsulation using dirty VM tricks as well. In C++, you can alwyas cast the object instance to get access to the underlying implementation. It is safe to say no languages encapsulation is effective against a truely determined effort to violate it.

There are two distinct forms of polymorphism. The first is that the same symbol can point to multiple functions. In C++ this is done using a table of function pointers. The second form is that two functions of the same name can take different sets of parameters and point to differnent implementations. This requires compiler support. In C++ this is implemented via Name mangling, where the types of the parameters and the return value are added to the symbol name. In Java, all inheritance is performed via a V table, and is scoped on the class name of the class that originally defined it.

What is modus ponens/tolens (sp)?

Forms of logical arguments. A->B A Therefore B is a modus ponens argument.

A modus tollens is a logical argument of the form A->B not(B) therefore not(A).

The truth table for A->B is:

A B==A->B

0 0 ==1

1 0 ==0 (logical contradiction)

1 1 ==1

0 1 ==1 (not(a) does not imply not(b))

What kinds of race conditions are there?

Wikipedia has a write up of these, but I never learned these terms.

What is a critical section?

A section of code that can only have a single thread of execution at a given point in time. Access to a critical section is controlled by a lock.

What is the difference between a monitor and a semaphore?

Both are methods of concurancy control. A semaphore performs concurrency control by keeping a counter of requests. THe counter is implemented using an atomic test and set. When the semaphore is 0, another process is granted the permission requested. All others will be required to wait.

A monitor is a compiler generated construct that controls access to a resource. A call to code that is a critical section will have code generated that acquires the lock, and then releases the lock after exiting the critical section.

The third form of concurrency control is message passing. These three forms are all equivalent. Each can be implemented in terms of the other two.

Define NP-complete.

A problem is NP if there is a solution that can be performed in polynomial time by a non-determinisitic turing machine. A solution to the problem can be verified in polynomial time by a deterministic Turing machine. A problem is NP complete if every other problem in NP can be reduced to that problem. NP-complete problems are the hardest problems in NP.

Java Native Interface

The reason I left Java programming was due to the type of work I got in that field. However, I love the language. It provides the programmer with the right set of tools to focus on getting the task done. Memory management, while important, is not the primary focus of each and every programming task.

Don Knuth’s quote about premature optimization being the root of all evil often comes to mind. C is a great language for low level tasks, for embedding code on a really small platform, and for ensuring that you can understand the end binaries format and structure. One nice thing about Java is that it, too has a rigidly defined and easy to understand binary format. So, one approach to problem programming might be to code in Java to solve the problem, then optimize in C.

The language binding between Java and is the Java Native Interface (JNI). JNI makes use of the Java ‘native’ keyword. a Native method is one implemented external to the current Java class.

Here is a trivial example:

public class Sample

{

   private native String reverse(String prompt);   static {

      System.loadLibrary("reverse");

   }

public static void main(String[] args)

      {

         Sample jn=new Sample();

System.out.println("Got "+ jn.reverse("Some Data"));

      }

}

The ‘native’ line defines the method reverse. To resolve this, the jvm will look for a symbol: Java_Sample_reverse. From this we can infer that
parameter polymorphism is either not supported, or the jvm only resorts to name mangling when required to deal ambiguous situations.

the nexts steps are 1) run javac to convert the .java file to a .class file. and 2)run javah on the .class file to generate a .h file for the c library.

The function definition looks like this:

JNIEXPORT jstring JNICALL Java_Sample_reverse
(JNIEnv *, jobject, jstring);

This is within an extern “C” block for C++code, so we don’t get C++ semantics for the function implementation. This means you won’t be able to make a single set of objects to be shared between C+++ and Java, but this would be unwieldy no matter what.

For gcc The JNIEXPORT is resolved away to nothing. This compiler directive is to support Microsoft’s compiler which forces you to declare if a function is going to be visible outside of the scope of the current file, pretty much the opposite of ‘static’. JNICALL also resolves to nothing, but I suspect on a windows platform it would introduce code that specifies the pascal function calling convention for handling parameters. JNIEnv is a pointer to a pointer, and thus must be used like this :
(*env)->doSomething();
C++ Provides operator overloading of the -> so you can refer using this semantic instead:
env->doSomething();

Note that the string gets passed as a jstring. jni.h shows this to be a jobject. jobject is a struct with nothing inside it. Thus, once we go from java to C++, we are not supposed to know what exists on the other side except from reading the specification.

For this example, I have a function that reverses the string passed in. Here it is:

#include 

#include 

#include 

#include /*

 * Class:     MyJni

 * Method:    getLine

 * Signature: (Ljava/lang/String;)Ljava/lang/String;

 */

JNIEXPORT jstring JNICALL Java_Sample_reverse

  (JNIEnv * env, jobject obj, jstring str)

{

   jstring retval;

   char * msg;

   int i;

   int len;

const char * orig = (*env)->GetStringUTFChars(env, str,0);

len = strlen(orig);

msg = (char *)malloc(len+1);

/*disregard the null termination fro now; it will not be copied.*/

   len--;

for (i = 0; i <= len; ++i){

      msg[i] = orig[len-i];

   }

   msg[i]=0;

(*env)->ReleaseStringUTFChars(env, str, orig);

retval = (*env)->NewStringUTF(env, msg);

free(msg);

return retval;

}

Here is the Makefile I used to build it.

CFLAGS+=-I/usr/lib/jvm/java-6-sun-1.6.0.00/include -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/linux
FILES=MyJni.h

all: libreverse.so Sample.class

.SUFFIXES : .c  .class .h .so .java

.class.h :
        javah $*

clean :
        rm -rf *.o *.so $(FILES) *~ *.class Sample.h

.java.class :
        javac $<

libreverse.so : Sample.h reverse.c
        gcc reverse.c -o $*.so -shared $(CFLAGS) -fPIC

test :
        LD_LIBRARY_PATH=. java Sample

$: make && make test
javac Sample.java
javah Sample
gcc reverse.c -o libreverse.so -shared -I/usr/lib/jvm/java-6-sun-1.6.0.00/include -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/linux -fPIC
LD_LIBRARY_PATH=. java Sample
Got ataD emoS

rpm and deb commands: files to packages and back

These two commands tell you which package owns a particular file for an RPM or DEB based system respectively.

rpmquery –whatprovides <path-to-file>

dpkg-query –search <path-to-file>

(The short form for dpkg is -S)

To list the files owned by a package use:

rpmquery –list <package>

dpkg-query -L <package>

(This long form for debian is –listfiles )

A useful utility to find all the other files in a package for a given binary (in this case lsof) is:

rpmquery –list $(rpmquery –whatprovides $(which lsof ) )

Or

dpkg-query -L $(dpkg-query –search $( which lsof ) | sed ‘s!\:.*!!’ )

Projects that need IPv6 support

Our project uses a bunch of open source packages. I’ve been looking through them and this seems to be the current state:

  • Linux Kernel: Good to go in both 2.4 and 2.6
  • OpenPegasus CIM Broker: IPV6 support is underway, but not yet implemented.
  • SBLIM SFCBD IPV6 Support is built in, based on a compile time switch
  • OpenIPMI: IPMI Tool won’t accept a valid IPv6 address. This is a slightly different code source than the rest of the project, so it doesn’t mean that the rest of it won’t support IPv6.
  • OpenWSMAN
  • OpenSSL: Claims to be agnostic of the IP level. Since Open SSH is build on OpenSSL, and OpenSSH works, it works for at least a subset of it’s functionality.
  • OpenSSH: Connecting via IPv6 Works Confirmed for both ssh and scp.  scp is a pain.
  • OpenSLP: Seems to have IPv6 support, but it isvery recent.  It requires IPv6 multicast support.  Multicast has often been an after thought in switch implementations, so IPv6 multicast may have issues in the future.

Computer Science GRE Prep

Once again I feel myself being draw to take that damn test. I am a software professional. This means I do about .001% computer science. Computer Science is math. It has nothing to do with computers except that it maybe explains what a computer would theoretically be able to do if it were infinitely big.

So I am going to try to use the blog as my notes for reviewing. One issue that comes up time and time again is combinations. Combinations are based on permutations. If you have n distinct items, they can be ordered in in n! ways. For the non math people, n! is n times n-1 times n-2 … times 1. 0! is defined as 1, as they claim there is only one way to order zero items…suspect, but it keeps the algorithms easy.

If you want to figure out how many permutations of length m you can make out of n items, where n>m, you have n (n-1)(n-2)…(n-m+1). This is equal to n!/(n-m)!

Combinations are like permutations, but order does not matter. Basically, a combination is a subset. If you have three items, and you want a subset of two items, you can take {1,2} {2,3} or {1,3}. This is called n choose m, where n is the number of items in the set, and m is the number of items in the subset. The formula for this is n!/(n-m)!m!. This makes sense as you take the formula for permutations and divide out the number of redundant combinations of length m.

One place where combinations are useful is in graph theory. There are many comparable problems in graph theory which can all be converted into each other. One of these is the clique problem. A clique is a completely connected subgraph.

META Comment: This version of WordPress as a blogging tool does not make it easy to draw pictures.

The clique problem is to determine if there is a clique of size m in a graph whose number of nodes is n, n>m. A brute force algorithm iterates through all subsets of nodes of size m and checks to see if them make a clique. Testing for a clique is not computationally intensive, but generating all of the subsets is O(n choose m).

Continuing support for IPv4 with a switch for IPv6

Although our product needs to support IPv6, it will be used by people in IPv4 mode for the near future. Since a call to the socket or bind system calls will fail if the underlying interface is not IPv6 enabled, we have to fall back to IPv6. So I am currently thinking we’ll have code like this:

int af_inet_version = AF_INET;

With code that can set that to AF_INET6 either read out of a config file or a command line argument.

Then later…

int rc = socket( af_inet_version, …);

And when calling bind, use af_inet_version to switch

Part of getting our product converted to IPv6 is project for reliable messaging. This code is no longer actively maintained. I’ve done a few simple greps through the code and agree with my co-worker who warned me that it is going to be quite tricky. Aside from the obvious calls to socket and bind, ISIS records addresses to be reused later. For example, In include/cl_inter.h the ioq structure contains

saddr io_address; /* Destination address */
saddr io_rcvaddr; /* Receive address (for statistics) */

where saddrs is a typedef in include/cl_typedefs.h

typedef struct sockaddr_in saddr;

I am thinking of an approach that would be to use a union:

struct sockaddress{
union{
struct sockaddr_in in;
struct sockaddr_in6 in6;
}addr;
};
struct sockaddress sin;
struct sockaddress pin;

switch(af_inet_version){
case AF_INET:
addrsize = sizeof(struct sockaddr_in);
sin.addr.in.sin_addr.s_addr = INADDR_ANY;
sin.addr.in.sin_port = htons(port);
sin.addr.in.sin_family = af_inet_version;
break;

case AF_INET6:
addrsize = sizeof(struct sockaddr_in6);
sin.addr.in6.sin6_addr = in6addr_any;
sin.addr.in6.sin6_port = htons(port);
sin.addr.in6.sin6_family = af_inet_version;
break;
}

I put the union inside a struct because I originally was going to put the AF_INET to AF_INET6 field into struct sockaddress. I may go back to that for the real code, and then I can support both IPv6 and IPv4 in a single system.

extracting files from an rpm

rpms are saved in a file format called cpio, with a few minor changes.  To convert an rpm to this format use rpm2cpio.  The cpio binary is responsible for manipulating these files.  So if you want to treat that rpm as just another archive, and extract the files in it, you can link a couple of tools.  Here’s the line:

rpm2cpio your.rpm | cpio -di

Back to Cannon

If you plan on climbing at Cannon cliff, try to find a climb other than Moby Grape.

When you exit the parking lot at the base of Cannon Cliff, you will see a box on right hand side where you are expected to leave a record of your party, your vehicle, and your planned climb. Before I placed my sheet in the slot, I scanned through the 7 or so sheets from parties ahead of us. Two were planning on climbing Whitney-Gilman, one had listed a couple difficult climbs, and four were planning on climbing Moby Grape.

The path to the cliff was different than I remembered from my last trip, back in 1993. After walking up and down the path a few times, looking for the cairn that was no longer there, I finally pulled out the guide book to see that we were supposed to hook a hard right on a small path right after the bridge. The hike up to the cliff comes up just to the right of the former site of the “Old Man of the Mountains.” The fog line was right at the base of the cliff, preventing us from really identifying any features on the cliff. Still, I knew that we were to the right of the start of Moby. So we walked left along the base of the cliff.

Cannon really is a tremendous piece of granite. The frost action is brutal there, ;leading to lots of rock fall each year. That means that it has a lot of interesting features. Walking past many of the other climbs, you could see multiple lines up, corners, roofs, cracks, and aretes.

The first pitch of Moby Grape has been replaced by a better start, a single pitch climb. Reppy’s crack is a 5.8 hand crack that would feel right at home in Yosemite. When we arrived, there was a party on the climb, with the second just visible at the top of the crack, and another party all ready to go. We took our time getting prepped, as we would have to wait for both the leader and the second, but we were in no rush. Even though the climb is 8 pitches, only a couple go at 5.8 and most are easier. I did realize that I had forgotten my headlamp, and Pete admitted that he didn’t have his either. The leader of the party just starting the climb was a new leader, and had gotten scared recently, and did not know how to crack climb. He made about five feet of vertical progress in twenty minutes. We decided to move to a different climb. We decided not to do the original start of Moby as it took larger gear than we had brought, and the crowds up higher were likely to be as bad as we had there on the ground. Instead, we moved over to Vertigo, a 5.9 a few hundred feet back toward the trail.

Actually, the first pitch was not Vertigo at all, but instead the first pitch of Union Jack. It was a clean, straight ahead 5.6 and Pete lead it with no trouble at all, setting up anchor a a pair of brand new bolts that would make the ASCA proud. The second pitch went at 5.8 and was mine. The first part was quite straight forward, interesting enough with a combo of crack and layback ending at a bolt. Yep, a bolt on Cannon. The bolt was there to let you lower out, and pendulum around the corner. I’ve done a little bit of aid climbing, and cheated on my share of climbs, but I don’t recall having to do a pendulum, and certainly not one as tricky as this. I had a goldlocks moment there: My first attempt was too high, my second was too low. My third was too high. But my fourth attempt was just right. I managed to grovel across the slab to the finger crack about 20 feet to my right and get up into the second part of the pitch. Due to the way the rope was running from the bolt, I had to run it out a bit before I could place another piece, but the crack was stellar, probably 5.7 climbing. I got stumped right before the anchor, and ended up hang-dogging the last move. It was a fairly physical sequence, and I was feeling pumped.  The two climbers ahead of use were rappelling down, and I ended up hanging out at the anchor with one of them.  Between their tale of the offwidth and the fact that I was freezing made me decided I did not want to complete the climb.  IT was Only 5.9, but I am pretty out of shape, my partner wasn’t going to lead it, and I was close to fried.

Instead, we rappelled one long 200′ rap to the ground and moved over to Slow and Easy.  This is a 5.8 crack on the left edge of the big wall area.  Pete gave it a quick attempt, but was shut down by the unfamiliar climbing style.  I gave it a go, and, although challenged by it, lead it clean.  I love crack climbing, in case you were wondering.

On the hike out, we walked down directly beneath the former site of the old man.  I turned and looked up ward and saw, silhouetted against the sky two cables.  They looked like  wipers that had been left up while someone cleaned the windshield.  I wondered which of the boulders we scrambled across had been part of New Hampshire’s icon.