hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From whe...@apache.org
Subject [15/19] hadoop git commit: HDFS-9170. Move libhdfs / fuse-dfs / libwebhdfs to hdfs-client. Contributed by Haohui Mai.
Date Wed, 07 Oct 2015 07:16:23 GMT
http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.c
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.c b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.c
new file mode 100644
index 0000000..d7bdfe7
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.c
@@ -0,0 +1,213 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#include <pthread.h>
+#include <grp.h>
+#include <pwd.h>
+#include <stdlib.h>
+
+#include "fuse_dfs.h"
+
+/*
+ * getpwuid and getgrgid return static structs so we safeguard the contents
+ * while retrieving fields using the 2 structs below.
+ * NOTE: if using both, always get the passwd struct firt!
+ */
+pthread_mutex_t passwdstruct_mutex = PTHREAD_MUTEX_INITIALIZER;
+pthread_mutex_t groupstruct_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+/*
+ * Utility for getting the user making the fuse call in char * form
+ * NOTE: if non-null return, the return must be freed by the caller.
+ */
+char *getUsername(uid_t uid) {
+  //
+  // Critical section - protect from concurrent calls in different threads.
+  // since the struct below is static.
+  // (no returns until end)
+  //
+
+  pthread_mutex_lock(&passwdstruct_mutex);
+
+  struct passwd *userinfo = getpwuid(uid);
+  char * ret = userinfo && userinfo->pw_name ? strdup(userinfo->pw_name) : NULL;
+
+  pthread_mutex_unlock(&passwdstruct_mutex);
+
+  //
+  // End critical section 
+  // 
+  return ret;
+}
+
+/**
+ * Cleans up a char ** group pointer
+ */
+
+void freeGroups(char **groups, int numgroups) {
+  if (groups == NULL) {
+    return;
+  }
+  int i ;
+  for (i = 0; i < numgroups; i++) {
+    free(groups[i]);
+  }
+  free(groups);
+}
+
+#define GROUPBUF_SIZE 5
+
+char *getGroup(gid_t gid) {
+  //
+  // Critical section - protect from concurrent calls in different threads.
+  // since the struct below is static.
+  // (no returns until end)
+  //
+
+  pthread_mutex_lock(&groupstruct_mutex);
+
+  struct group* grp = getgrgid(gid);
+  char * ret = grp && grp->gr_name ? strdup(grp->gr_name) : NULL;
+
+  //
+  // End critical section 
+  // 
+  pthread_mutex_unlock(&groupstruct_mutex);
+
+  return ret;
+}
+
+
+/**
+ * Utility for getting the group from the uid
+ * NOTE: if non-null return, the return must be freed by the caller.
+ */
+char *getGroupUid(uid_t uid) {
+  //
+  // Critical section - protect from concurrent calls in different threads
+  // since the structs below are static.
+  // (no returns until end)
+  //
+
+  pthread_mutex_lock(&passwdstruct_mutex);
+  pthread_mutex_lock(&groupstruct_mutex);
+
+  char *ret = NULL;
+  struct passwd *userinfo = getpwuid(uid);
+  if (NULL != userinfo) {
+    struct group* grp = getgrgid( userinfo->pw_gid);
+    ret = grp && grp->gr_name ? strdup(grp->gr_name) : NULL;
+  }
+
+  //
+  // End critical section 
+  // 
+  pthread_mutex_unlock(&groupstruct_mutex);
+  pthread_mutex_unlock(&passwdstruct_mutex);
+
+  return ret;
+}
+
+
+/**
+ * lookup the gid based on the uid
+ */
+gid_t getGidUid(uid_t uid) {
+  //
+  // Critical section - protect from concurrent calls in different threads
+  // since the struct below is static.
+  // (no returns until end)
+  //
+
+  pthread_mutex_lock(&passwdstruct_mutex);
+
+  struct passwd *userinfo = getpwuid(uid);
+  gid_t gid = userinfo == NULL ? 0 : userinfo->pw_gid;
+
+  //
+  // End critical section 
+  // 
+  pthread_mutex_unlock(&passwdstruct_mutex);
+
+  return gid;
+}
+
+/**
+ * Utility for getting the groups for the user making the fuse call in char * form
+ */
+char ** getGroups(uid_t uid, int *num_groups)
+{
+  char *user = getUsername(uid);
+
+  if (user == NULL)
+    return NULL;
+
+  char **groupnames = NULL;
+
+  // see http://www.openldap.org/lists/openldap-devel/199903/msg00023.html
+
+  //#define GETGROUPS_T 1 
+#ifdef GETGROUPS_T
+  *num_groups = GROUPBUF_SIZE;
+
+  gid_t* grouplist = malloc(GROUPBUF_SIZE * sizeof(gid_t)); 
+  assert(grouplist != NULL);
+  gid_t* tmp_grouplist; 
+  int rtr;
+
+  gid_t gid = getGidUid(uid);
+
+  if ((rtr = getgrouplist(user, gid, grouplist, num_groups)) == -1) {
+    // the buffer we passed in is < *num_groups
+    if ((tmp_grouplist = realloc(grouplist, *num_groups * sizeof(gid_t))) != NULL) {
+      grouplist = tmp_grouplist;
+      getgrouplist(user, gid, grouplist, num_groups);
+    }
+  }
+
+  groupnames = (char**)malloc(sizeof(char*)* (*num_groups) + 1);
+  assert(groupnames);
+  int i;
+  for (i=0; i < *num_groups; i++)  {
+    groupnames[i] = getGroup(grouplist[i]);
+    if (groupnames[i] == NULL) {
+      ERROR("Could not lookup group %d\n", (int)grouplist[i]);
+    }
+  } 
+  free(grouplist);
+  assert(user != NULL);
+  groupnames[i] = user;
+  *num_groups = *num_groups + 1;
+#else
+
+  int i = 0;
+  assert(user != NULL);
+  groupnames[i] = user;
+  i++;
+
+  groupnames[i] = getGroupUid(uid);
+  if (groupnames[i]) {
+    i++;
+  }
+
+  *num_groups = i;
+
+#endif
+  return groupnames;
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.h
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.h b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.h
new file mode 100644
index 0000000..d63d916
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/fuse_users.h
@@ -0,0 +1,70 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __FUSE_USERS_H__
+#define __FUSE_USERS_H__
+
+#include <grp.h>
+#include <pwd.h>
+#include <pthread.h>
+
+/**
+ * Overall Note:
+ * 1. all these functions should be thread safe.
+ * 2. the ones that return char * or char **, generally require
+ * the caller to free the return value.
+ *
+ */
+
+
+/**
+ * Utility for getting the user making the fuse call in char * form
+ * NOTE: if non-null return, the return must be freed by the caller.
+ */
+char *getUsername(uid_t uid);
+
+
+/**
+ * Cleans up a char ** group pointer
+ */
+void freeGroups(char **groups, int numgroups);
+
+/**
+ * Lookup single group. Caller responsible for free of the return value
+ */
+char *getGroup(gid_t gid);
+
+/**
+ * Utility for getting the group from the uid
+ * NOTE: if non-null return, the return must be freed by the caller.
+ */
+char *getGroupUid(uid_t uid) ;
+
+
+/**
+ * lookup the gid based on the uid
+ */
+
+gid_t getGidUid(uid_t uid);
+
+/**
+ * Utility for getting the groups for the user making the fuse call in char * form
+ */
+char ** getGroups(uid_t uid, int *num_groups);
+
+#endif

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/TestFuseDFS.java
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/TestFuseDFS.java b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/TestFuseDFS.java
new file mode 100644
index 0000000..a5d9abd
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/TestFuseDFS.java
@@ -0,0 +1,410 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.*;
+import java.net.URI;
+import java.util.ArrayList;
+import java.util.concurrent.atomic.*;
+
+import org.apache.log4j.Level;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.fs.permission.*;
+import org.apache.hadoop.hdfs.*;
+import org.apache.hadoop.io.IOUtils;
+import org.apache.hadoop.test.GenericTestUtils;
+import org.apache.hadoop.util.StringUtils;
+
+import org.junit.Test;
+import org.junit.BeforeClass;
+import org.junit.AfterClass;
+import static org.junit.Assert.*;
+
+/**
+ * Basic functional tests on a fuse-dfs mount.
+ */
+public class TestFuseDFS {
+
+  private static MiniDFSCluster cluster;
+  private static FileSystem fs;
+  private static Process fuseProcess;
+  private static Runtime r;
+  private static String mountPoint;
+
+  private static final Log LOG = LogFactory.getLog(TestFuseDFS.class);
+  {
+    GenericTestUtils.setLogLevel(LOG, Level.ALL);
+  }
+
+  /** Dump the given intput stream to stderr */
+  private static void dumpInputStream(InputStream is) throws IOException {
+    int len;
+    do {
+      byte b[] = new byte[is.available()];
+      len = is.read(b);
+      System.out.println("Read "+len+" bytes");
+      System.out.write(b, 0, b.length);
+    } while (len > 0);
+  }
+
+  /** 
+   * Wait for the given process to return and check that it exited
+   * as required. Log if the process failed.
+   */
+  private static void checkProcessRet(Process p, boolean expectPass) 
+      throws IOException {
+    try {
+      int ret = p.waitFor();
+      if (ret != 0) {
+	dumpInputStream(p.getErrorStream());
+      }
+      if (expectPass) {
+	assertEquals(0, ret);
+      } else {
+	assertTrue(ret != 0);
+      }
+    } catch (InterruptedException ie) {
+      fail("Process interrupted: "+ie.getMessage());
+    }
+  }
+
+  /** Exec the given command and assert it executed successfully */
+  private static void execWaitRet(String cmd) throws IOException {
+    LOG.debug("EXEC "+cmd);
+    Process p = r.exec(cmd);
+    try {
+      p.waitFor();
+    } catch (InterruptedException ie) {
+      fail("Process interrupted: "+ie.getMessage());
+    }
+  }
+
+  /** Exec the given command and assert it executed successfully */
+  private static void execIgnoreRet(String cmd) throws IOException {
+    LOG.debug("EXEC "+cmd);
+    r.exec(cmd);
+  }
+
+  /** Exec the given command and assert it executed successfully */
+  private static void execAssertSucceeds(String cmd) throws IOException {
+    LOG.debug("EXEC "+cmd);
+    checkProcessRet(r.exec(cmd), true);
+  }
+
+  /** Exec the given command, assert it returned an error code */
+  private static void execAssertFails(String cmd) throws IOException {
+    LOG.debug("EXEC "+cmd);
+    checkProcessRet(r.exec(cmd), false);
+  }
+
+  /** Create and write the given file */
+  private static void createFile(File f, String s) throws IOException {
+    InputStream is = new ByteArrayInputStream(s.getBytes());
+    FileOutputStream fos = new FileOutputStream(f);
+    IOUtils.copyBytes(is, fos, s.length(), true);
+  }
+
+  /** Check that the given file exists with the given contents */
+  private static void checkFile(File f, String expectedContents) 
+      throws IOException {
+    FileInputStream fi = new FileInputStream(f);
+    int len = expectedContents.length();
+    byte[] b = new byte[len];
+    try {
+      IOUtils.readFully(fi, b, 0, len);
+    } catch (IOException ie) {
+      fail("Reading "+f.getName()+" failed with "+ie.getMessage());
+    } finally {
+      fi.close(); // NB: leaving f unclosed prevents unmount
+    }
+    String s = new String(b, 0, len);
+    assertEquals("File content differs", expectedContents, s);
+  }
+
+  private static class RedirectToStdoutThread extends Thread {
+    private InputStream is;
+
+    RedirectToStdoutThread(InputStream is) {
+      this.is = is;
+    }
+    public void run() {
+      try {
+        InputStreamReader isr = new InputStreamReader(is);
+        BufferedReader br = new BufferedReader(isr);
+        String line=null;
+        while ( (line = br.readLine()) != null) {
+          LOG.error("FUSE_LINE:" + line);
+        }
+      } catch (IOException e) {
+        e.printStackTrace();
+      }
+    }
+  }
+
+  /** Run a fuse-dfs process to mount the given DFS */
+  private static Process establishMount(URI uri) throws IOException  {
+    Runtime r = Runtime.getRuntime();
+    String cp = System.getProperty("java.class.path");
+
+    String buildTestDir = System.getProperty("build.test");
+    String fuseCmd = buildTestDir + "/../fuse_dfs";
+    String libHdfs = buildTestDir + "/../../../c++/lib";
+
+    String arch = System.getProperty("os.arch");
+    String jvm = System.getProperty("java.home") + "/lib/" + arch + "/server";
+    String lp = System.getProperty("LD_LIBRARY_PATH")+":"+libHdfs+":"+jvm;
+    LOG.debug("LD_LIBRARY_PATH=" + lp);
+
+    String nameNode = 
+      "dfs://" + uri.getHost() + ":" + String.valueOf(uri.getPort());
+
+    // NB: We're mounting via an unprivileged user, therefore
+    // user_allow_other needs to be set in /etc/fuse.conf, which also
+    // needs to be world readable.
+    String mountCmd[] = {
+      fuseCmd, nameNode, mountPoint,
+      // "-odebug",              // Don't daemonize
+      "-obig_writes",            // Allow >4kb writes
+      "-oentry_timeout=0.1",     // Don't cache dents long
+      "-oattribute_timeout=0.1", // Don't cache attributes long
+      "-ononempty",              // Don't complain about junk in mount point
+      "-f",                      // Don't background the process
+      "-ordbuffer=32768",        // Read buffer size in kb
+      "rw"
+    };
+
+    String [] env = {
+      "CLASSPATH="+cp,
+      "LD_LIBRARY_PATH="+lp,
+      "PATH=/usr/bin:/bin"
+    };
+
+    execWaitRet("fusermount -u " + mountPoint);
+    execAssertSucceeds("rm -rf " + mountPoint);
+    execAssertSucceeds("mkdir -p " + mountPoint);
+
+    // Mount the mini cluster
+    String cmdStr = "";
+    for (String c : mountCmd) {
+      cmdStr += (" " + c);
+    }
+    LOG.info("now mounting with:" + cmdStr);
+    Process fuseProcess = r.exec(mountCmd, env);
+    RedirectToStdoutThread stdoutThread =
+      new RedirectToStdoutThread(fuseProcess.getInputStream());
+    RedirectToStdoutThread stderrThread =
+      new RedirectToStdoutThread(fuseProcess.getErrorStream());
+    stdoutThread.start();
+    stderrThread.start();
+    // Wait for fusermount to start up, so that we know we're operating on the
+    // FUSE FS when we run the tests.
+    try {
+      Thread.sleep(50000);
+    } catch (InterruptedException e) {
+    }
+    return fuseProcess;
+  }
+
+  /** Tear down the fuse-dfs process and mount */
+  private static void teardownMount() throws IOException {
+    execWaitRet("fusermount -u " + mountPoint);
+    try {
+      assertEquals(0, fuseProcess.waitFor()); // fuse_dfs should exit cleanly
+    } catch (InterruptedException e) {
+      fail("interrupted while waiting for fuse_dfs process to exit.");
+    }
+  }
+
+  @BeforeClass
+  public static void startUp() throws IOException {
+    Configuration conf = new HdfsConfiguration();
+    r = Runtime.getRuntime();
+    mountPoint = System.getProperty("build.test") + "/mnt";
+    conf.setBoolean(DFSConfigKeys.DFS_PERMISSIONS_ENABLED_KEY, false);
+    cluster = new MiniDFSCluster.Builder(conf).build();
+    cluster.waitClusterUp();
+    fs = cluster.getFileSystem();
+    fuseProcess = establishMount(fs.getUri());
+  }
+
+  @AfterClass
+  public static void tearDown() throws IOException {
+    // Unmount before taking down the mini cluster
+    // so no outstanding operations hang.
+    teardownMount();
+    if (fs != null) {
+      fs.close();
+    }
+    if (cluster != null) {
+      cluster.shutdown();
+    }
+  }
+
+  /** Test basic directory creation, access, removal */
+  @Test
+  public void testBasicDir() throws IOException {
+    File d = new File(mountPoint, "dir1");
+
+    // Mkdir, access and rm via the mount
+    execAssertSucceeds("mkdir " + d.getAbsolutePath());
+    execAssertSucceeds("ls " + d.getAbsolutePath());
+    execAssertSucceeds("rmdir " + d.getAbsolutePath());
+
+    // The dir should no longer exist
+    execAssertFails("ls " + d.getAbsolutePath());
+  }
+
+  /** Test basic file creation and writing */
+  @Test
+  public void testCreate() throws IOException {
+    final String contents = "hello world";
+    File f = new File(mountPoint, "file1");
+
+    // Create and access via the mount
+    createFile(f, contents);
+
+    // XX avoids premature EOF
+    try {
+      Thread.sleep(1000);
+    } catch (InterruptedException ie) { }
+
+    checkFile(f, contents);
+
+    // Cat, stat and delete via the mount
+    execAssertSucceeds("cat " + f.getAbsolutePath());
+    execAssertSucceeds("stat " + f.getAbsolutePath());
+    execAssertSucceeds("rm " + f.getAbsolutePath());
+
+    // The file should no longer exist
+    execAssertFails("ls " + f.getAbsolutePath());
+  }
+
+  /** Test creating a file via touch */
+  @Test
+  public void testTouch() throws IOException {
+    File f = new File(mountPoint, "file1");
+    execAssertSucceeds("touch " + f.getAbsolutePath());
+    execAssertSucceeds("rm " + f.getAbsolutePath());
+  }
+
+  /** Test random access to a file */
+  @Test
+  public void testRandomAccess() throws IOException {
+    final String contents = "hello world";
+    File f = new File(mountPoint, "file1");
+
+    createFile(f, contents);
+
+    RandomAccessFile raf = new RandomAccessFile(f, "rw");
+    raf.seek(f.length());
+    try {
+      raf.write('b');
+    } catch (IOException e) {
+      // Expected: fuse-dfs not yet support append
+      assertEquals("Operation not supported", e.getMessage());
+    } finally {
+      raf.close();
+    }
+
+    raf = new RandomAccessFile(f, "rw");
+    raf.seek(0);
+    try {
+      raf.write('b');
+      fail("Over-wrote existing bytes");
+    } catch (IOException e) {
+      // Expected: can-not overwrite a file
+      assertEquals("Invalid argument", e.getMessage());
+    } finally {
+      raf.close();
+    }
+    execAssertSucceeds("rm " + f.getAbsolutePath());
+  }
+
+  /** Test copying a set of files from the mount to itself */
+  @Test
+  public void testCopyFiles() throws IOException {
+    final String contents = "hello world";
+    File d1 = new File(mountPoint, "dir1");
+    File d2 = new File(mountPoint, "dir2");
+
+    // Create and populate dir1 via the mount
+    execAssertSucceeds("mkdir " + d1.getAbsolutePath());
+    for (int i = 0; i < 5; i++) {
+      createFile(new File(d1, "file"+i), contents);
+    }
+    assertEquals(5, d1.listFiles().length);
+
+    // Copy dir from the mount to the mount
+    execAssertSucceeds("cp -r " + d1.getAbsolutePath() +
+                       " " + d2.getAbsolutePath());
+    assertEquals(5, d2.listFiles().length);
+
+    // Access all the files in the dirs and remove them
+    execAssertSucceeds("find " + d1.getAbsolutePath());
+    execAssertSucceeds("find " + d2.getAbsolutePath());
+    execAssertSucceeds("rm -r " + d1.getAbsolutePath());
+    execAssertSucceeds("rm -r " + d2.getAbsolutePath());
+  }
+
+  /** Test concurrent creation and access of the mount */
+  @Test
+  public void testMultipleThreads() throws IOException {
+    ArrayList<Thread> threads = new ArrayList<Thread>();
+    final AtomicReference<String> errorMessage = new AtomicReference<String>();
+
+    for (int i = 0; i < 10; i++) {
+      Thread t = new Thread() {
+	  public void run() {
+	    try {
+	      File d = new File(mountPoint, "dir"+getId());
+	      execWaitRet("mkdir " + d.getAbsolutePath());
+	      for (int j = 0; j < 10; j++) {
+		File f = new File(d, "file"+j);
+		final String contents = "thread "+getId()+" "+j;
+		createFile(f, contents);
+	      }
+	      for (int j = 0; j < 10; j++) {
+		File f = new File(d, "file"+j);
+		execWaitRet("cat " + f.getAbsolutePath());
+		execWaitRet("rm " + f.getAbsolutePath());
+	      }
+	      execWaitRet("rmdir " + d.getAbsolutePath());
+	    } catch (IOException ie) {
+	      errorMessage.set(
+		String.format("Exception %s", 
+			      StringUtils.stringifyException(ie)));
+	    }
+          }
+	};
+      t.start();
+      threads.add(t);
+    }
+
+    for (Thread t : threads) {
+      try {
+	t.join();
+      } catch (InterruptedException ie) {
+	fail("Thread interrupted: "+ie.getMessage());
+      }
+    }
+
+    assertNull(errorMessage.get(), errorMessage.get());
+  }
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.c
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.c b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.c
new file mode 100644
index 0000000..78fdbc6
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.c
@@ -0,0 +1,403 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define FUSE_USE_VERSION 26
+
+#include "fuse-dfs/test/fuse_workload.h"
+#include "libhdfs/expect.h"
+#include "util/posix_util.h"
+
+#include <dirent.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <fuse.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/statvfs.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <utime.h>
+
+typedef int (*testReadDirFn)(const struct dirent *de, void *v);
+
+struct fileCtx {
+  int fd;
+  char *str;
+  int strLen;
+  char *path;
+};
+
+static const char *DIRS_A_AND_B[] = { "a", "b", NULL };
+static const char *DIRS_B_AND_C[] = { "b", "c", NULL };
+
+#define LONG_STR_LEN 1024
+#define NUM_FILE_CTX 3
+#define MAX_TRIES 120
+
+// TODO: implement/test access, mknod, symlink
+// TODO: rmdir on non-dir, non-empty dir
+// TODO: test unlink-during-writing
+// TODO: test weird open flags failing
+// TODO: test chown, chmod
+
+static int testReadDirImpl(DIR *dp, testReadDirFn fn, void *data)
+{
+  struct dirent *de;
+  int ret, noda = 0;
+
+  while (1) {
+    de = readdir(dp);
+    if (!de)
+      return noda;
+    if (!strcmp(de->d_name, "."))
+      continue;
+    if (!strcmp(de->d_name, ".."))
+      continue;
+    ret = fn(de, data);
+    if (ret < 0)
+      return ret;
+    ++noda;
+  }
+  return noda;
+}
+
+static int testReadDir(const char *dirName, testReadDirFn fn, void *data)
+{
+  int ret;
+  DIR *dp;
+
+  dp = opendir(dirName);
+  if (!dp) {
+    return -errno;
+  }
+  ret = testReadDirImpl(dp, fn, data);
+  closedir(dp);
+  return ret;
+}
+
+static int expectDirs(const struct dirent *de, void *v)
+{
+  const char **names = v;
+  const char **n;
+
+  for (n = names; *n; ++n) {
+    if (!strcmp(de->d_name, *n)) {
+      return 0;
+    }
+  }
+  return -ENOENT;
+}
+
+static int safeWrite(int fd, const void *buf, size_t amt)
+{
+  while (amt > 0) {
+    int r = write(fd, buf, amt);
+    if (r < 0) {
+      if (errno != EINTR)
+        return -errno;
+      continue;
+    }
+    amt -= r;
+    buf = (const char *)buf + r;
+  }
+  return 0;
+}
+
+static int safeRead(int fd, void *buf, int c)
+{
+  int res;
+  size_t amt = 0;
+
+  while (amt < c) {
+    res = read(fd, buf, c - amt);
+    if (res <= 0) {
+      if (res == 0)
+        return amt;
+      if (errno != EINTR)
+        return -errno;
+      continue;
+    }
+    amt += res;
+    buf = (char *)buf + res;
+  }
+  return amt;
+}
+
+/* Bug: HDFS-2551.
+ * When a program writes a file, closes it, and immediately re-opens it,
+ * it might not appear to have the correct length.  This is because FUSE
+ * invokes the release() callback asynchronously.
+ *
+ * To work around this, we keep retrying until the file length is what we
+ * expect.
+ */
+static int closeWorkaroundHdfs2551(int fd, const char *path, off_t expectedSize)
+{
+  int ret, try;
+  struct stat stBuf;
+
+  RETRY_ON_EINTR_GET_ERRNO(ret, close(fd));
+  EXPECT_ZERO(ret);
+  for (try = 0; try < MAX_TRIES; try++) {
+    EXPECT_ZERO(stat(path, &stBuf));
+    EXPECT_NONZERO(S_ISREG(stBuf.st_mode));
+    if (stBuf.st_size == expectedSize) {
+      return 0;
+    }
+    sleepNoSig(1);
+  }
+  fprintf(stderr, "FUSE_WORKLOAD: error: expected file %s to have length "
+          "%lld; instead, it had length %lld\n",
+          path, (long long)expectedSize, (long long)stBuf.st_size);
+  return -EIO;
+}
+
+#ifdef FUSE_CAP_ATOMIC_O_TRUNC
+
+/**
+ * Test that we can create a file, write some contents to it, close that file,
+ * and then successfully re-open with O_TRUNC.
+ */
+static int testOpenTrunc(const char *base)
+{
+  int fd, err;
+  char path[PATH_MAX];
+  const char * const SAMPLE1 = "this is the first file that we wrote.";
+  const char * const SAMPLE2 = "this is the second file that we wrote.  "
+    "It's #2!";
+
+  snprintf(path, sizeof(path), "%s/trunc.txt", base);
+  fd = open(path, O_CREAT | O_TRUNC | O_WRONLY, 0644);
+  if (fd < 0) {
+    err = errno;
+    fprintf(stderr, "TEST_ERROR: testOpenTrunc(%s): first open "
+            "failed with error %d\n", path, err);
+    return -err;
+  }
+  EXPECT_ZERO(safeWrite(fd, SAMPLE1, strlen(SAMPLE1)));
+  EXPECT_ZERO(closeWorkaroundHdfs2551(fd, path, strlen(SAMPLE1)));
+  fd = open(path, O_CREAT | O_TRUNC | O_WRONLY, 0644);
+  if (fd < 0) {
+    err = errno;
+    fprintf(stderr, "TEST_ERROR: testOpenTrunc(%s): second open "
+            "failed with error %d\n", path, err);
+    return -err;
+  }
+  EXPECT_ZERO(safeWrite(fd, SAMPLE2, strlen(SAMPLE2)));
+  EXPECT_ZERO(closeWorkaroundHdfs2551(fd, path, strlen(SAMPLE2)));
+  return 0;
+}
+
+#else
+
+static int testOpenTrunc(const char *base)
+{
+  fprintf(stderr, "FUSE_WORKLOAD: We lack FUSE_CAP_ATOMIC_O_TRUNC support.  "
+          "Not testing open(O_TRUNC).\n");
+  return 0;
+}
+
+#endif
+
+int runFuseWorkloadImpl(const char *root, const char *pcomp,
+    struct fileCtx *ctx)
+{
+  char base[PATH_MAX], tmp[PATH_MAX], *tmpBuf;
+  char src[PATH_MAX], dst[PATH_MAX];
+  struct stat stBuf;
+  int ret, i;
+  struct utimbuf tbuf;
+  struct statvfs stvBuf;
+
+  // The root must be a directory
+  EXPECT_ZERO(stat(root, &stBuf));
+  EXPECT_NONZERO(S_ISDIR(stBuf.st_mode));
+
+  // base = <root>/<pcomp>.  base must not exist yet
+  snprintf(base, sizeof(base), "%s/%s", root, pcomp);
+  EXPECT_NEGATIVE_ONE_WITH_ERRNO(stat(base, &stBuf), ENOENT);
+
+  // mkdir <base>
+  RETRY_ON_EINTR_GET_ERRNO(ret, mkdir(base, 0755));
+  EXPECT_ZERO(ret);
+
+  // rmdir <base>
+  RETRY_ON_EINTR_GET_ERRNO(ret, rmdir(base));
+  EXPECT_ZERO(ret);
+
+  // mkdir <base>
+  RETRY_ON_EINTR_GET_ERRNO(ret, mkdir(base, 0755));
+  EXPECT_ZERO(ret);
+
+  // stat <base>
+  EXPECT_ZERO(stat(base, &stBuf));
+  EXPECT_NONZERO(S_ISDIR(stBuf.st_mode));
+
+  // mkdir <base>/a
+  snprintf(tmp, sizeof(tmp), "%s/a", base);
+  RETRY_ON_EINTR_GET_ERRNO(ret, mkdir(tmp, 0755));
+  EXPECT_ZERO(ret);
+
+  /* readdir test */
+  EXPECT_INT_EQ(1, testReadDir(base, expectDirs, DIRS_A_AND_B));
+
+  // mkdir <base>/b
+  snprintf(tmp, sizeof(tmp), "%s/b", base);
+  RETRY_ON_EINTR_GET_ERRNO(ret, mkdir(tmp, 0755));
+  EXPECT_ZERO(ret);
+
+  // readdir a and b
+  EXPECT_INT_EQ(2, testReadDir(base, expectDirs, DIRS_A_AND_B));
+
+  // rename a -> c
+  snprintf(src, sizeof(src), "%s/a", base);
+  snprintf(dst, sizeof(dst), "%s/c", base);
+  EXPECT_ZERO(rename(src, dst));
+
+  // readdir c and b
+  EXPECT_INT_EQ(-ENOENT, testReadDir(base, expectDirs, DIRS_A_AND_B));
+  EXPECT_INT_EQ(2, testReadDir(base, expectDirs, DIRS_B_AND_C));
+
+  // statvfs
+  memset(&stvBuf, 0, sizeof(stvBuf));
+  EXPECT_ZERO(statvfs(root, &stvBuf));
+
+  // set utime on base
+  memset(&tbuf, 0, sizeof(tbuf));
+  tbuf.actime = 123;
+  tbuf.modtime = 456;
+  EXPECT_ZERO(utime(base, &tbuf));
+
+  // stat(base)
+  EXPECT_ZERO(stat(base, &stBuf));
+  EXPECT_NONZERO(S_ISDIR(stBuf.st_mode));
+  //EXPECT_INT_EQ(456, stBuf.st_atime); // hdfs doesn't store atime on directories
+  EXPECT_INT_EQ(456, stBuf.st_mtime);
+
+  // open some files and write to them
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    snprintf(tmp, sizeof(tmp), "%s/b/%d", base, i);
+    ctx[i].path = strdup(tmp);
+    if (!ctx[i].path) {
+      fprintf(stderr, "FUSE_WORKLOAD: OOM on line %d\n", __LINE__);
+      return -ENOMEM;
+    }
+    ctx[i].strLen = strlen(ctx[i].str);
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    ctx[i].fd = open(ctx[i].path, O_RDONLY);
+    if (ctx[i].fd >= 0) {
+      fprintf(stderr, "FUSE_WORKLOAD: Error: was able to open %s for read before it "
+              "was created!\n", ctx[i].path);
+      return -EIO; 
+    }
+    ctx[i].fd = creat(ctx[i].path, 0755);
+    if (ctx[i].fd < 0) {
+      fprintf(stderr, "FUSE_WORKLOAD: Failed to create file %s for writing!\n",
+              ctx[i].path);
+      return -EIO;
+    }
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    EXPECT_ZERO(safeWrite(ctx[i].fd, ctx[i].str, ctx[i].strLen));
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    EXPECT_ZERO(closeWorkaroundHdfs2551(ctx[i].fd, ctx[i].path, ctx[i].strLen));
+    ctx[i].fd = -1;
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    ctx[i].fd = open(ctx[i].path, O_RDONLY);
+    if (ctx[i].fd < 0) {
+      fprintf(stderr, "FUSE_WORKLOAD: Failed to open file %s for reading!\n",
+              ctx[i].path);
+      return -EIO;
+    }
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    tmpBuf = calloc(1, ctx[i].strLen);
+    if (!tmpBuf) {
+      fprintf(stderr, "FUSE_WORKLOAD: OOM on line %d\n", __LINE__);
+      return -ENOMEM;
+    }
+    EXPECT_INT_EQ(ctx[i].strLen, safeRead(ctx[i].fd, tmpBuf, ctx[i].strLen));
+    EXPECT_ZERO(memcmp(ctx[i].str, tmpBuf, ctx[i].strLen));
+    RETRY_ON_EINTR_GET_ERRNO(ret, close(ctx[i].fd));
+    ctx[i].fd = -1;
+    EXPECT_ZERO(ret);
+    free(tmpBuf);
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    EXPECT_ZERO(truncate(ctx[i].path, 0));
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    EXPECT_ZERO(stat(ctx[i].path, &stBuf));
+    EXPECT_NONZERO(S_ISREG(stBuf.st_mode));
+    EXPECT_INT_EQ(0, stBuf.st_size);
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    RETRY_ON_EINTR_GET_ERRNO(ret, unlink(ctx[i].path));
+    EXPECT_ZERO(ret);
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    EXPECT_NEGATIVE_ONE_WITH_ERRNO(stat(ctx[i].path, &stBuf), ENOENT);
+  }
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    free(ctx[i].path);
+  }
+  EXPECT_ZERO(testOpenTrunc(base));
+  EXPECT_ZERO(recursiveDelete(base));
+  return 0;
+}
+
+int runFuseWorkload(const char *root, const char *pcomp)
+{
+  int ret, err;
+  size_t i;
+  char longStr[LONG_STR_LEN];
+  struct fileCtx ctx[NUM_FILE_CTX] = {
+    {
+      .fd = -1,
+      .str = "hello, world",
+    },
+    {
+      .fd = -1,
+      .str = "A",
+    },
+    {
+      .fd = -1,
+      .str = longStr,
+    },
+  };
+  for (i = 0; i < LONG_STR_LEN - 1; i++) {
+    longStr[i] = 'a' + (i % 10);
+  }
+  longStr[LONG_STR_LEN - 1] = '\0';
+
+  ret = runFuseWorkloadImpl(root, pcomp, ctx);
+  // Make sure all file descriptors are closed, or else we won't be able to
+  // unmount
+  for (i = 0; i < NUM_FILE_CTX; i++) {
+    if (ctx[i].fd >= 0) {
+      RETRY_ON_EINTR_GET_ERRNO(err, close(ctx[i].fd));
+    }
+  }
+  return ret;
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.h
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.h b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.h
new file mode 100644
index 0000000..3ff2dc4
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/fuse_workload.h
@@ -0,0 +1,36 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __FUSE_WORKLOAD_H__
+#define __FUSE_WORKLOAD_H__
+
+/**
+ * Perform some FUSE operations.
+ *
+ * The operations will be performed under <root>/<pcomp>.
+ * This directory should not exist prior to the test, and should not be used by
+ * any other tests concurrently.
+ *
+ * @param root             The root directory for the testing.
+ * @param pcomp            Path component to add to root
+ *
+ * @return                 0 on success; negative error code otherwise
+ */
+int runFuseWorkload(const char *root, const char *pcomp);
+
+#endif

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/test_fuse_dfs.c
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/test_fuse_dfs.c b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/test_fuse_dfs.c
new file mode 100644
index 0000000..f4212a6
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/test/test_fuse_dfs.c
@@ -0,0 +1,378 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "fuse-dfs/test/fuse_workload.h"
+#include "libhdfs/expect.h"
+#include "libhdfs/hdfs.h"
+#include "libhdfs/native_mini_dfs.h"
+#include "util/posix_util.h"
+
+#include <ctype.h>
+#include <errno.h>
+#include <libgen.h>
+#include <limits.h>
+#include <mntent.h>
+#include <semaphore.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <time.h>
+#include <unistd.h>
+
+/** Exit status to return when there is an exec error.
+ *
+ * We assume that fusermount and fuse_dfs don't normally return this error code.
+ */
+#define EXIT_STATUS_EXEC_ERROR 240
+
+/** Maximum number of times to try to unmount the fuse filesystem we created.
+ */
+#define MAX_UNMOUNT_TRIES 20
+
+/**
+ * Verify that the fuse workload works on the local FS.
+ *
+ * @return        0 on success; error code otherwise
+ */
+static int verifyFuseWorkload(void)
+{
+  char tempDir[PATH_MAX];
+
+  EXPECT_ZERO(createTempDir(tempDir, sizeof(tempDir), 0755));
+  EXPECT_ZERO(runFuseWorkload(tempDir, "test"));
+  EXPECT_ZERO(recursiveDelete(tempDir));
+
+  return 0;
+}
+
+static int fuserMount(int *procRet, ...) __attribute__((sentinel));
+
+/**
+ * Invoke the fusermount binary.
+ *
+ * @param retVal  (out param) The return value from fusermount
+ *
+ * @return        0 on success; error code if the fork fails
+ */
+static int fuserMount(int *procRet, ...)
+{
+  int ret, status;
+  size_t i = 0;
+  char *args[64], *c;
+  va_list ap;
+  pid_t pid, pret;
+
+  args[i++] = "fusermount";
+  va_start(ap, procRet);
+  while (1) {
+    c = va_arg(ap, char *);
+    args[i++] = c;
+    if (!c)
+      break;
+    if (i > sizeof(args)/sizeof(args[0])) {
+      va_end(ap);
+      return -EINVAL;
+    }
+  }
+  va_end(ap);
+  pid = fork();
+  if (pid < 0) {
+    ret = errno;
+    fprintf(stderr, "FUSE_TEST: failed to fork: error %d: %s\n",
+            ret, strerror(ret));
+    return -ret;
+  } else if (pid == 0) {
+    if (execvp("fusermount", args)) {
+      ret = errno;
+      fprintf(stderr, "FUSE_TEST: failed to execute fusermount: "
+              "error %d: %s\n", ret, strerror(ret));
+      exit(EXIT_STATUS_EXEC_ERROR);
+    }
+  }
+  pret = waitpid(pid, &status, 0);
+  if (pret != pid) {
+    ret = errno;
+    fprintf(stderr, "FUSE_TEST: failed to wait for pid %d: returned %d "
+            "(error %d: %s)\n", pid, pret, ret, strerror(ret));
+    return -ret;
+  }
+  if (WIFEXITED(status)) {
+    *procRet = WEXITSTATUS(status);
+  } else if (WIFSIGNALED(status)) {
+    fprintf(stderr, "FUSE_TEST: fusermount exited with signal %d\n",
+            WTERMSIG(status));
+    *procRet = -1;
+  } else {
+    fprintf(stderr, "FUSE_TEST: fusermount exited with unknown exit type\n");
+    *procRet = -1;
+  }
+  return 0;
+}
+
+static int isMounted(const char *mntPoint)
+{
+  int ret;
+  FILE *fp;
+  struct mntent *mntEnt;
+
+  fp = setmntent("/proc/mounts", "r");
+  if (!fp) {
+    ret = errno;
+    fprintf(stderr, "FUSE_TEST: isMounted(%s) failed to open /proc/mounts: "
+            "error %d: %s", mntPoint, ret, strerror(ret));
+    return -ret;
+  }
+  while ((mntEnt = getmntent(fp))) {
+    if (!strcmp(mntEnt->mnt_dir, mntPoint)) {
+      endmntent(fp);
+      return 1;
+    }
+  }
+  endmntent(fp);
+  return 0;
+}
+
+static int waitForMount(const char *mntPoint, int retries)
+{
+  int ret, try = 0;
+
+  while (try++ < retries) {
+    ret = isMounted(mntPoint);
+    if (ret < 0) {
+      fprintf(stderr, "FUSE_TEST: waitForMount(%s, %d): isMounted returned "
+              "error %d\n", mntPoint, retries, ret);
+    } else if (ret == 1) {
+      return 0;
+    }
+    sleepNoSig(2);
+  }
+  return -ETIMEDOUT;
+}
+
+/**
+ * Try to unmount the fuse filesystem we mounted.
+ *
+ * Normally, only one try should be sufficient to unmount the filesystem.
+ * However, if our tests needs to exit right after starting the fuse_dfs process,
+ * the fuse_dfs process might not have gotten around to mounting itself yet.  The
+ * retry loop in this function ensures that we always unmount FUSE before
+ * exiting, rather than leaving around a zombie fuse_dfs.
+ *
+ * @param mntPoint            Where the FUSE filesystem is mounted
+ * @return                    0 on success; error code otherwise
+ */
+static int cleanupFuse(const char *mntPoint)
+{
+  int ret, pret, tries = 0;
+
+  while (1) {
+    ret = fuserMount(&pret, "-u", mntPoint, NULL);
+    if (ret) {
+      fprintf(stderr, "FUSE_TEST: unmountFuse: failed to invoke fuserMount: "
+              "error %d\n", ret);
+      return ret;
+    }
+    if (pret == 0) {
+      fprintf(stderr, "FUSE_TEST: successfully unmounted FUSE filesystem.\n");
+      return 0;
+    }
+    if (tries++ > MAX_UNMOUNT_TRIES) {
+      return -EIO;
+    }
+    fprintf(stderr, "FUSE_TEST: retrying unmount in 2 seconds...\n");
+    sleepNoSig(2);
+  }
+}
+
+/**
+ * Create a fuse_dfs process using the miniDfsCluster we set up.
+ *
+ * @param argv0                 argv[0], as passed into main
+ * @param cluster               The NativeMiniDfsCluster to connect to
+ * @param mntPoint              The mount point
+ * @param pid                   (out param) the fuse_dfs process
+ *
+ * @return                      0 on success; error code otherwise
+ */
+static int spawnFuseServer(const char *argv0,
+    const struct NativeMiniDfsCluster *cluster, const char *mntPoint,
+    pid_t *pid)
+{
+  int ret, procRet;
+  char scratch[PATH_MAX], *dir, fusePath[PATH_MAX], portOpt[128];
+
+  snprintf(scratch, sizeof(scratch), "%s", argv0);
+  dir = dirname(scratch);
+  snprintf(fusePath, sizeof(fusePath), "%s/fuse_dfs", dir);
+  if (access(fusePath, X_OK)) {
+    fprintf(stderr, "FUSE_TEST: spawnFuseServer: failed to find fuse_dfs "
+            "binary at %s!\n", fusePath);
+    return -ENOENT;
+  }
+  /* Let's make sure no other FUSE filesystem is mounted at mntPoint */
+  ret = fuserMount(&procRet, "-u", mntPoint, NULL);
+  if (ret) {
+    fprintf(stderr, "FUSE_TEST: fuserMount -u %s failed with error %d\n",
+            mntPoint, ret);
+    return -EIO;
+  }
+  if (procRet == EXIT_STATUS_EXEC_ERROR) {
+    fprintf(stderr, "FUSE_TEST: fuserMount probably could not be executed\n");
+    return -EIO;
+  }
+  /* fork and exec the fuse_dfs process */
+  *pid = fork();
+  if (*pid < 0) {
+    ret = errno;
+    fprintf(stderr, "FUSE_TEST: spawnFuseServer: failed to fork: "
+            "error %d: %s\n", ret, strerror(ret));
+    return -ret;
+  } else if (*pid == 0) {
+    snprintf(portOpt, sizeof(portOpt), "-oport=%d",
+             nmdGetNameNodePort(cluster));
+    if (execl(fusePath, fusePath, "-obig_writes", "-oserver=hdfs://localhost",
+          portOpt, "-onopermissions", "-ononempty", "-oinitchecks",
+          mntPoint, "-f", NULL)) {
+      ret = errno;
+      fprintf(stderr, "FUSE_TEST: spawnFuseServer: failed to execv %s: "
+              "error %d: %s\n", fusePath, ret, strerror(ret));
+      exit(EXIT_STATUS_EXEC_ERROR);
+    }
+  }
+  return 0;
+}
+
+/**
+ * Test that we can start up fuse_dfs and do some stuff.
+ */
+int main(int argc, char **argv)
+{
+  int ret, pret, status;
+  pid_t fusePid;
+  const char *mntPoint;
+  char mntTmp[PATH_MAX] = "";
+  struct NativeMiniDfsCluster* tlhCluster;
+  struct NativeMiniDfsConf conf = {
+      .doFormat = 1,
+  };
+
+  mntPoint = getenv("TLH_FUSE_MNT_POINT");
+  if (!mntPoint) {
+    if (createTempDir(mntTmp, sizeof(mntTmp), 0755)) {
+      fprintf(stderr, "FUSE_TEST: failed to create temporary directory for "
+              "fuse mount point.\n");
+      ret = EXIT_FAILURE;
+      goto done;
+    }
+    fprintf(stderr, "FUSE_TEST: creating mount point at '%s'\n", mntTmp);
+    mntPoint = mntTmp;
+  }
+  if (verifyFuseWorkload()) {
+    fprintf(stderr, "FUSE_TEST: failed to verify fuse workload on "
+            "local FS.\n");
+    ret = EXIT_FAILURE;
+    goto done_rmdir;
+  }
+  tlhCluster = nmdCreate(&conf);
+  if (!tlhCluster) {
+    ret = EXIT_FAILURE;
+    goto done_rmdir;
+  }
+  if (nmdWaitClusterUp(tlhCluster)) {
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  ret = spawnFuseServer(argv[0], tlhCluster, mntPoint, &fusePid);
+  if (ret) {
+    fprintf(stderr, "FUSE_TEST: spawnFuseServer failed with error "
+            "code %d\n", ret);
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  ret = waitForMount(mntPoint, 20);
+  if (ret) {
+    fprintf(stderr, "FUSE_TEST: waitForMount(%s) failed with error "
+            "code %d\n", mntPoint, ret);
+    cleanupFuse(mntPoint);
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  ret = runFuseWorkload(mntPoint, "test");
+  if (ret) {
+    fprintf(stderr, "FUSE_TEST: runFuseWorkload failed with error "
+            "code %d\n", ret);
+    cleanupFuse(mntPoint);
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  if (cleanupFuse(mntPoint)) {
+    fprintf(stderr, "FUSE_TEST: fuserMount -u %s failed with error "
+            "code %d\n", mntPoint, ret);
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  alarm(120);
+  pret = waitpid(fusePid, &status, 0);
+  if (pret != fusePid) {
+    ret = errno;
+    fprintf(stderr, "FUSE_TEST: failed to wait for fusePid %d: "
+            "returned %d: error %d (%s)\n",
+            fusePid, pret, ret, strerror(ret));
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  if (WIFEXITED(status)) {
+    ret = WEXITSTATUS(status);
+    if (ret) {
+      fprintf(stderr, "FUSE_TEST: fuse exited with failure status "
+              "%d!\n", ret);
+      ret = EXIT_FAILURE;
+      goto done_nmd_shutdown;
+    }
+  } else if (WIFSIGNALED(status)) {
+    ret = WTERMSIG(status);
+    if (ret != SIGTERM) {
+      fprintf(stderr, "FUSE_TEST: fuse exited with unexpected "
+              "signal %d!\n", ret);
+      ret = EXIT_FAILURE;
+      goto done_nmd_shutdown;
+    }
+  } else {
+    fprintf(stderr, "FUSE_TEST: fusermount exited with unknown exit type\n");
+    ret = EXIT_FAILURE;
+    goto done_nmd_shutdown;
+  }
+  ret = EXIT_SUCCESS;
+
+done_nmd_shutdown:
+  EXPECT_ZERO(nmdShutdown(tlhCluster));
+  nmdFree(tlhCluster);
+done_rmdir:
+  if (mntTmp[0]) {
+    rmdir(mntTmp);
+  }
+done:
+  if (ret == EXIT_SUCCESS) {
+    fprintf(stderr, "FUSE_TEST: SUCCESS.\n");
+  } else {
+    fprintf(stderr, "FUSE_TEST: FAILURE!\n");
+  }
+  return ret;
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.c
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.c b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.c
new file mode 100644
index 0000000..59308a5
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.c
@@ -0,0 +1,155 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "util/posix_util.h"
+
+#include <dirent.h>
+#include <errno.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <limits.h>
+
+static pthread_mutex_t gTempdirLock = PTHREAD_MUTEX_INITIALIZER;
+
+static int gTempdirNonce = 0;
+
+int recursiveDeleteContents(const char *path)
+{
+  int ret;
+  DIR *dp;
+  struct dirent *de;
+  char tmp[PATH_MAX];
+
+  dp = opendir(path);
+  if (!dp) {
+    ret = -errno;
+    fprintf(stderr, "recursiveDelete(%s) failed with error %d\n", path, ret);
+    return ret;
+  }
+  while (1) {
+    de = readdir(dp);
+    if (!de) {
+      ret = 0;
+      break;
+    }
+    if ((de->d_name[0] == '.') && (de->d_name[1] == '\0'))
+      continue;
+    if ((de->d_name[0] == '.') && (de->d_name[1] == '.') &&
+        (de->d_name[2] == '\0'))
+      continue;
+    snprintf(tmp, sizeof(tmp), "%s/%s", path, de->d_name);
+    ret = recursiveDelete(tmp);
+    if (ret)
+      break;
+  }
+  if (closedir(dp)) {
+    ret = -errno;
+    fprintf(stderr, "recursiveDelete(%s): closedir failed with "
+            "error %d\n", path, ret);
+    return ret;
+  }
+  return ret;
+}
+
+/*
+ * Simple recursive delete implementation.
+ * It could be optimized, but there is no need at the moment.
+ * TODO: use fstat, etc.
+ */
+int recursiveDelete(const char *path)
+{
+  int ret;
+  struct stat stBuf;
+
+  ret = stat(path, &stBuf);
+  if (ret != 0) {
+    ret = -errno;
+    fprintf(stderr, "recursiveDelete(%s): stat failed with "
+            "error %d\n", path, ret);
+    return ret;
+  }
+  if (S_ISDIR(stBuf.st_mode)) {
+    ret = recursiveDeleteContents(path);
+    if (ret)
+      return ret;
+    ret = rmdir(path);
+    if (ret) {
+      ret = errno;
+      fprintf(stderr, "recursiveDelete(%s): rmdir failed with error %d\n",
+              path, ret);
+      return ret;
+    }
+  } else {
+    ret = unlink(path);
+    if (ret) {
+      ret = -errno;
+      fprintf(stderr, "recursiveDelete(%s): unlink failed with "
+              "error %d\n", path, ret);
+      return ret;
+    }
+  }
+  return 0;
+}
+
+int createTempDir(char *tempDir, int nameMax, int mode)
+{
+  char tmp[PATH_MAX];
+  int pid, nonce;
+  const char *base = getenv("TMPDIR");
+  if (!base)
+    base = "/tmp";
+  if (base[0] != '/') {
+    // canonicalize non-absolute TMPDIR
+    if (realpath(base, tmp) == NULL) {
+      return -errno;
+    }
+    base = tmp;
+  }
+  pid = getpid();
+  pthread_mutex_lock(&gTempdirLock);
+  nonce = gTempdirNonce++;
+  pthread_mutex_unlock(&gTempdirLock);
+  snprintf(tempDir, nameMax, "%s/temp.%08d.%08d", base, pid, nonce);
+  if (mkdir(tempDir, mode) == -1) {
+    int ret = errno;
+    return -ret;
+  }
+  return 0;
+}
+
+void sleepNoSig(int sec)
+{
+  int ret;
+  struct timespec req, rem;
+
+  rem.tv_sec = sec;
+  rem.tv_nsec = 0;
+  do {
+    req = rem;
+    ret = nanosleep(&req, &rem);
+  } while ((ret == -1) && (errno == EINTR));
+  if (ret == -1) {
+    ret = errno;
+    fprintf(stderr, "nanosleep error %d (%s)\n", ret, strerror(ret));
+  }
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.h
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.h b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.h
new file mode 100644
index 0000000..c184c26
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/posix_util.h
@@ -0,0 +1,58 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __POSIX_UTIL_H__
+#define __POSIX_UTIL_H__
+
+/**
+ * Recursively delete the contents of a directory
+ *
+ * @param path      directory whose contents we should delete
+ *
+ * @return          0 on success; error code otherwise
+ */
+int recursiveDeleteContents(const char *path);
+
+/**
+ * Recursively delete a local path, using unlink or rmdir as appropriate.
+ *
+ * @param path      path to delete
+ *
+ * @return          0 on success; error code otherwise
+ */
+int recursiveDelete(const char *path);
+
+/**
+ * Get a temporary directory 
+ *
+ * @param tempDir   (out param) path to the temporary directory
+ * @param nameMax   Length of the tempDir buffer
+ * @param mode      Mode to create with
+ *
+ * @return          0 on success; error code otherwise
+ */
+int createTempDir(char *tempDir, int nameMax, int mode);
+
+/**
+ * Sleep without using signals
+ *
+ * @param sec       Number of seconds to sleep
+ */
+void sleepNoSig(int sec);
+
+#endif

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/tree.h
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/tree.h b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/tree.h
new file mode 100644
index 0000000..ac78ee3
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/fuse-dfs/util/tree.h
@@ -0,0 +1,765 @@
+/*	$NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $	*/
+/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
+/* $FreeBSD: src/sys/sys/tree.h,v 1.9.4.1 2011/09/23 00:51:37 kensmith Exp $ */
+
+/*-
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef	_SYS_TREE_H_
+#define	_SYS_TREE_H_
+
+#include <sys/cdefs.h>
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure.  Every operation
+ * on the tree causes a splay to happen.  The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree.  On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n).  The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute.  It fulfills a set of conditions:
+ *	- every search path from the root to a leaf consists of the
+ *	  same number of black nodes,
+ *	- each red node (except for the root) has a black parent,
+ *	- each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type)						\
+struct name {								\
+	struct type *sph_root; /* root of the tree */			\
+}
+
+#define SPLAY_INITIALIZER(root)						\
+	{ NULL }
+
+#define SPLAY_INIT(root) do {						\
+	(root)->sph_root = NULL;					\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ENTRY(type)						\
+struct {								\
+	struct type *spe_left; /* left element */			\
+	struct type *spe_right; /* right element */			\
+}
+
+#define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
+#define SPLAY_ROOT(head)		(head)->sph_root
+#define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
+	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
+	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
+	(head)->sph_root = tmp;						\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
+	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
+	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
+	(head)->sph_root = tmp;						\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do {				\
+	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
+	tmp = (head)->sph_root;						\
+	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do {				\
+	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
+	tmp = (head)->sph_root;						\
+	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
+	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
+	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
+	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp)				\
+void name##_SPLAY(struct name *, struct type *);			\
+void name##_SPLAY_MINMAX(struct name *, int);				\
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
+									\
+/* Finds the node with the same key as elm */				\
+static __inline struct type *						\
+name##_SPLAY_FIND(struct name *head, struct type *elm)			\
+{									\
+	if (SPLAY_EMPTY(head))						\
+		return(NULL);						\
+	name##_SPLAY(head, elm);					\
+	if ((cmp)(elm, (head)->sph_root) == 0)				\
+		return (head->sph_root);				\
+	return (NULL);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
+{									\
+	name##_SPLAY(head, elm);					\
+	if (SPLAY_RIGHT(elm, field) != NULL) {				\
+		elm = SPLAY_RIGHT(elm, field);				\
+		while (SPLAY_LEFT(elm, field) != NULL) {		\
+			elm = SPLAY_LEFT(elm, field);			\
+		}							\
+	} else								\
+		elm = NULL;						\
+	return (elm);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_MIN_MAX(struct name *head, int val)			\
+{									\
+	name##_SPLAY_MINMAX(head, val);					\
+        return (SPLAY_ROOT(head));					\
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp)				\
+struct type *								\
+name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
+{									\
+    if (SPLAY_EMPTY(head)) {						\
+	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
+    } else {								\
+	    int __comp;							\
+	    name##_SPLAY(head, elm);					\
+	    __comp = (cmp)(elm, (head)->sph_root);			\
+	    if(__comp < 0) {						\
+		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
+		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
+	    } else if (__comp > 0) {					\
+		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
+		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
+	    } else							\
+		    return ((head)->sph_root);				\
+    }									\
+    (head)->sph_root = (elm);						\
+    return (NULL);							\
+}									\
+									\
+struct type *								\
+name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
+{									\
+	struct type *__tmp;						\
+	if (SPLAY_EMPTY(head))						\
+		return (NULL);						\
+	name##_SPLAY(head, elm);					\
+	if ((cmp)(elm, (head)->sph_root) == 0) {			\
+		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
+			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+		} else {						\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+			name##_SPLAY(head, elm);			\
+			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
+		}							\
+		return (elm);						\
+	}								\
+	return (NULL);							\
+}									\
+									\
+void									\
+name##_SPLAY(struct name *head, struct type *elm)			\
+{									\
+	struct type __node, *__left, *__right, *__tmp;			\
+	int __comp;							\
+\
+	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+	__left = __right = &__node;					\
+\
+	while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {		\
+		if (__comp < 0) {					\
+			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if ((cmp)(elm, __tmp) < 0){			\
+				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
+				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKLEFT(head, __right, field);		\
+		} else if (__comp > 0) {				\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if ((cmp)(elm, __tmp) > 0){			\
+				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
+				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKRIGHT(head, __left, field);		\
+		}							\
+	}								\
+	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
+}									\
+									\
+/* Splay with either the minimum or the maximum element			\
+ * Used to find minimum or maximum element in tree.			\
+ */									\
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{									\
+	struct type __node, *__left, *__right, *__tmp;			\
+\
+	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+	__left = __right = &__node;					\
+\
+	while (1) {							\
+		if (__comp < 0) {					\
+			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if (__comp < 0){				\
+				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
+				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKLEFT(head, __right, field);		\
+		} else if (__comp > 0) {				\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if (__comp > 0) {				\
+				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
+				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKRIGHT(head, __left, field);		\
+		}							\
+	}								\
+	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
+}
+
+#define SPLAY_NEGINF	-1
+#define SPLAY_INF	1
+
+#define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
+					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
+					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head)					\
+	for ((x) = SPLAY_MIN(name, head);				\
+	     (x) != NULL;						\
+	     (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type)						\
+struct name {								\
+	struct type *rbh_root; /* root of the tree */			\
+}
+
+#define RB_INITIALIZER(root)						\
+	{ NULL }
+
+#define RB_INIT(root) do {						\
+	(root)->rbh_root = NULL;					\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_BLACK	0
+#define RB_RED		1
+#define RB_ENTRY(type)							\
+struct {								\
+	struct type *rbe_left;		/* left element */		\
+	struct type *rbe_right;		/* right element */		\
+	struct type *rbe_parent;	/* parent element */		\
+	int rbe_color;			/* node color */		\
+}
+
+#define RB_LEFT(elm, field)		(elm)->field.rbe_left
+#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
+#define RB_PARENT(elm, field)		(elm)->field.rbe_parent
+#define RB_COLOR(elm, field)		(elm)->field.rbe_color
+#define RB_ROOT(head)			(head)->rbh_root
+#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do {					\
+	RB_PARENT(elm, field) = parent;					\
+	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
+	RB_COLOR(elm, field) = RB_RED;					\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_SET_BLACKRED(black, red, field) do {				\
+	RB_COLOR(black, field) = RB_BLACK;				\
+	RB_COLOR(red, field) = RB_RED;					\
+} while (/*CONSTCOND*/ 0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x)	do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
+	(tmp) = RB_RIGHT(elm, field);					\
+	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
+		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
+	}								\
+	RB_AUGMENT(elm);						\
+	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
+		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
+			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
+		else							\
+			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
+	} else								\
+		(head)->rbh_root = (tmp);				\
+	RB_LEFT(tmp, field) = (elm);					\
+	RB_PARENT(elm, field) = (tmp);					\
+	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
+	(tmp) = RB_LEFT(elm, field);					\
+	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
+		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
+	}								\
+	RB_AUGMENT(elm);						\
+	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
+		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
+			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
+		else							\
+			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
+	} else								\
+		(head)->rbh_root = (tmp);				\
+	RB_RIGHT(tmp, field) = (elm);					\
+	RB_PARENT(elm, field) = (tmp);					\
+	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+#define	RB_PROTOTYPE(name, type, field, cmp)				\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
+attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
+attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
+attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
+attr struct type *name##_RB_FIND(struct name *, struct type *);		\
+attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
+attr struct type *name##_RB_NEXT(struct type *);			\
+attr struct type *name##_RB_PREV(struct type *);			\
+attr struct type *name##_RB_MINMAX(struct name *, int);			\
+									\
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define	RB_GENERATE(name, type, field, cmp)				\
+	RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define	RB_GENERATE_STATIC(name, type, field, cmp)			\
+	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
+attr void								\
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+{									\
+	struct type *parent, *gparent, *tmp;				\
+	while ((parent = RB_PARENT(elm, field)) != NULL &&		\
+	    RB_COLOR(parent, field) == RB_RED) {			\
+		gparent = RB_PARENT(parent, field);			\
+		if (parent == RB_LEFT(gparent, field)) {		\
+			tmp = RB_RIGHT(gparent, field);			\
+			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
+				RB_COLOR(tmp, field) = RB_BLACK;	\
+				RB_SET_BLACKRED(parent, gparent, field);\
+				elm = gparent;				\
+				continue;				\
+			}						\
+			if (RB_RIGHT(parent, field) == elm) {		\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				tmp = parent;				\
+				parent = elm;				\
+				elm = tmp;				\
+			}						\
+			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
+		} else {						\
+			tmp = RB_LEFT(gparent, field);			\
+			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
+				RB_COLOR(tmp, field) = RB_BLACK;	\
+				RB_SET_BLACKRED(parent, gparent, field);\
+				elm = gparent;				\
+				continue;				\
+			}						\
+			if (RB_LEFT(parent, field) == elm) {		\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				tmp = parent;				\
+				parent = elm;				\
+				elm = tmp;				\
+			}						\
+			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
+		}							\
+	}								\
+	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
+}									\
+									\
+attr void								\
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{									\
+	struct type *tmp;						\
+	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
+	    elm != RB_ROOT(head)) {					\
+		if (RB_LEFT(parent, field) == elm) {			\
+			tmp = RB_RIGHT(parent, field);			\
+			if (RB_COLOR(tmp, field) == RB_RED) {		\
+				RB_SET_BLACKRED(tmp, parent, field);	\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				tmp = RB_RIGHT(parent, field);		\
+			}						\
+			if ((RB_LEFT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+			    (RB_RIGHT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+				RB_COLOR(tmp, field) = RB_RED;		\
+				elm = parent;				\
+				parent = RB_PARENT(elm, field);		\
+			} else {					\
+				if (RB_RIGHT(tmp, field) == NULL ||	\
+				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+					struct type *oleft;		\
+					if ((oleft = RB_LEFT(tmp, field)) \
+					    != NULL)			\
+						RB_COLOR(oleft, field) = RB_BLACK;\
+					RB_COLOR(tmp, field) = RB_RED;	\
+					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+					tmp = RB_RIGHT(parent, field);	\
+				}					\
+				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
+				if (RB_RIGHT(tmp, field))		\
+					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				elm = RB_ROOT(head);			\
+				break;					\
+			}						\
+		} else {						\
+			tmp = RB_LEFT(parent, field);			\
+			if (RB_COLOR(tmp, field) == RB_RED) {		\
+				RB_SET_BLACKRED(tmp, parent, field);	\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				tmp = RB_LEFT(parent, field);		\
+			}						\
+			if ((RB_LEFT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+			    (RB_RIGHT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+				RB_COLOR(tmp, field) = RB_RED;		\
+				elm = parent;				\
+				parent = RB_PARENT(elm, field);		\
+			} else {					\
+				if (RB_LEFT(tmp, field) == NULL ||	\
+				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+					struct type *oright;		\
+					if ((oright = RB_RIGHT(tmp, field)) \
+					    != NULL)			\
+						RB_COLOR(oright, field) = RB_BLACK;\
+					RB_COLOR(tmp, field) = RB_RED;	\
+					RB_ROTATE_LEFT(head, tmp, oright, field);\
+					tmp = RB_LEFT(parent, field);	\
+				}					\
+				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
+				if (RB_LEFT(tmp, field))		\
+					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				elm = RB_ROOT(head);			\
+				break;					\
+			}						\
+		}							\
+	}								\
+	if (elm)							\
+		RB_COLOR(elm, field) = RB_BLACK;			\
+}									\
+									\
+attr struct type *							\
+name##_RB_REMOVE(struct name *head, struct type *elm)			\
+{									\
+	struct type *child, *parent, *old = elm;			\
+	int color;							\
+	if (RB_LEFT(elm, field) == NULL)				\
+		child = RB_RIGHT(elm, field);				\
+	else if (RB_RIGHT(elm, field) == NULL)				\
+		child = RB_LEFT(elm, field);				\
+	else {								\
+		struct type *left;					\
+		elm = RB_RIGHT(elm, field);				\
+		while ((left = RB_LEFT(elm, field)) != NULL)		\
+			elm = left;					\
+		child = RB_RIGHT(elm, field);				\
+		parent = RB_PARENT(elm, field);				\
+		color = RB_COLOR(elm, field);				\
+		if (child)						\
+			RB_PARENT(child, field) = parent;		\
+		if (parent) {						\
+			if (RB_LEFT(parent, field) == elm)		\
+				RB_LEFT(parent, field) = child;		\
+			else						\
+				RB_RIGHT(parent, field) = child;	\
+			RB_AUGMENT(parent);				\
+		} else							\
+			RB_ROOT(head) = child;				\
+		if (RB_PARENT(elm, field) == old)			\
+			parent = elm;					\
+		(elm)->field = (old)->field;				\
+		if (RB_PARENT(old, field)) {				\
+			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+				RB_LEFT(RB_PARENT(old, field), field) = elm;\
+			else						\
+				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+			RB_AUGMENT(RB_PARENT(old, field));		\
+		} else							\
+			RB_ROOT(head) = elm;				\
+		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
+		if (RB_RIGHT(old, field))				\
+			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
+		if (parent) {						\
+			left = parent;					\
+			do {						\
+				RB_AUGMENT(left);			\
+			} while ((left = RB_PARENT(left, field)) != NULL); \
+		}							\
+		goto color;						\
+	}								\
+	parent = RB_PARENT(elm, field);					\
+	color = RB_COLOR(elm, field);					\
+	if (child)							\
+		RB_PARENT(child, field) = parent;			\
+	if (parent) {							\
+		if (RB_LEFT(parent, field) == elm)			\
+			RB_LEFT(parent, field) = child;			\
+		else							\
+			RB_RIGHT(parent, field) = child;		\
+		RB_AUGMENT(parent);					\
+	} else								\
+		RB_ROOT(head) = child;					\
+color:									\
+	if (color == RB_BLACK)						\
+		name##_RB_REMOVE_COLOR(head, parent, child);		\
+	return (old);							\
+}									\
+									\
+/* Inserts a node into the RB tree */					\
+attr struct type *							\
+name##_RB_INSERT(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp;						\
+	struct type *parent = NULL;					\
+	int comp = 0;							\
+	tmp = RB_ROOT(head);						\
+	while (tmp) {							\
+		parent = tmp;						\
+		comp = (cmp)(elm, parent);				\
+		if (comp < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	RB_SET(elm, parent, field);					\
+	if (parent != NULL) {						\
+		if (comp < 0)						\
+			RB_LEFT(parent, field) = elm;			\
+		else							\
+			RB_RIGHT(parent, field) = elm;			\
+		RB_AUGMENT(parent);					\
+	} else								\
+		RB_ROOT(head) = elm;					\
+	name##_RB_INSERT_COLOR(head, elm);				\
+	return (NULL);							\
+}									\
+									\
+/* Finds the node with the same key as elm */				\
+attr struct type *							\
+name##_RB_FIND(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	int comp;							\
+	while (tmp) {							\
+		comp = cmp(elm, tmp);					\
+		if (comp < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	return (NULL);							\
+}									\
+									\
+/* Finds the first node greater than or equal to the search key */	\
+attr struct type *							\
+name##_RB_NFIND(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	struct type *res = NULL;					\
+	int comp;							\
+	while (tmp) {							\
+		comp = cmp(elm, tmp);					\
+		if (comp < 0) {						\
+			res = tmp;					\
+			tmp = RB_LEFT(tmp, field);			\
+		}							\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	return (res);							\
+}									\
+									\
+/* ARGSUSED */								\
+attr struct type *							\
+name##_RB_NEXT(struct type *elm)					\
+{									\
+	if (RB_RIGHT(elm, field)) {					\
+		elm = RB_RIGHT(elm, field);				\
+		while (RB_LEFT(elm, field))				\
+			elm = RB_LEFT(elm, field);			\
+	} else {							\
+		if (RB_PARENT(elm, field) &&				\
+		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
+			elm = RB_PARENT(elm, field);			\
+		else {							\
+			while (RB_PARENT(elm, field) &&			\
+			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+				elm = RB_PARENT(elm, field);		\
+			elm = RB_PARENT(elm, field);			\
+		}							\
+	}								\
+	return (elm);							\
+}									\
+									\
+/* ARGSUSED */								\
+attr struct type *							\
+name##_RB_PREV(struct type *elm)					\
+{									\
+	if (RB_LEFT(elm, field)) {					\
+		elm = RB_LEFT(elm, field);				\
+		while (RB_RIGHT(elm, field))				\
+			elm = RB_RIGHT(elm, field);			\
+	} else {							\
+		if (RB_PARENT(elm, field) &&				\
+		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
+			elm = RB_PARENT(elm, field);			\
+		else {							\
+			while (RB_PARENT(elm, field) &&			\
+			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+				elm = RB_PARENT(elm, field);		\
+			elm = RB_PARENT(elm, field);			\
+		}							\
+	}								\
+	return (elm);							\
+}									\
+									\
+attr struct type *							\
+name##_RB_MINMAX(struct name *head, int val)				\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	struct type *parent = NULL;					\
+	while (tmp) {							\
+		parent = tmp;						\
+		if (val < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else							\
+			tmp = RB_RIGHT(tmp, field);			\
+	}								\
+	return (parent);						\
+}
+
+#define RB_NEGINF	-1
+#define RB_INF	1
+
+#define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
+#define RB_PREV(name, x, y)	name##_RB_PREV(y)
+#define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head)					\
+	for ((x) = RB_MIN(name, head);					\
+	     (x) != NULL;						\
+	     (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_FROM(x, name, y)					\
+	for ((x) = (y);							\
+	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y)				\
+	for ((x) = RB_MIN(name, head);					\
+	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head)				\
+	for ((x) = RB_MAX(name, head);					\
+	     (x) != NULL;						\
+	     (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y)				\
+	for ((x) = (y);							\
+	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
+	for ((x) = RB_MAX(name, head);					\
+	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
+	     (x) = (y))
+
+#endif	/* _SYS_TREE_H_ */

http://git-wip-us.apache.org/repos/asf/hadoop/blob/3112f263/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/libhdfs/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/libhdfs/CMakeLists.txt b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/libhdfs/CMakeLists.txt
new file mode 100644
index 0000000..772a864
--- /dev/null
+++ b/hadoop-hdfs-project/hadoop-hdfs-native-client/src/main/native/libhdfs/CMakeLists.txt
@@ -0,0 +1,141 @@
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+add_definitions(-DLIBHDFS_DLL_EXPORT)
+
+include_directories(
+    ${GENERATED_JAVAH}
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_BINARY_DIR}
+    ${JNI_INCLUDE_DIRS}
+    main/native
+    main/native/libhdfs
+    ${OS_DIR}
+)
+
+hadoop_add_dual_library(hdfs
+    exception.c
+    jni_helper.c
+    hdfs.c
+    common/htable.c
+    ${OS_DIR}/mutexes.c
+    ${OS_DIR}/thread_local_storage.c
+)
+if(NEED_LINK_DL)
+   set(LIB_DL dl)
+endif()
+
+hadoop_target_link_dual_libraries(hdfs
+    ${JAVA_JVM_LIBRARY}
+    ${LIB_DL}
+    ${OS_LINK_LIBRARIES}
+)
+
+hadoop_dual_output_directory(hdfs ${OUT_DIR})
+set(LIBHDFS_VERSION "0.0.0")
+set_target_properties(hdfs PROPERTIES
+    SOVERSION ${LIBHDFS_VERSION})
+
+add_executable(test_libhdfs_ops
+    test/test_libhdfs_ops.c
+)
+target_link_libraries(test_libhdfs_ops
+    hdfs_static
+    ${JAVA_JVM_LIBRARY}
+)
+
+add_executable(test_libhdfs_read
+    test/test_libhdfs_read.c
+)
+target_link_libraries(test_libhdfs_read
+    hdfs_static
+    ${JAVA_JVM_LIBRARY}
+)
+
+add_executable(test_libhdfs_write
+    test/test_libhdfs_write.c
+)
+target_link_libraries(test_libhdfs_write
+    hdfs_static
+    ${JAVA_JVM_LIBRARY}
+)
+
+add_library(native_mini_dfs
+    native_mini_dfs.c
+    common/htable.c
+    exception.c
+    jni_helper.c
+    ${OS_DIR}/mutexes.c
+    ${OS_DIR}/thread_local_storage.c
+)
+target_link_libraries(native_mini_dfs
+    ${JAVA_JVM_LIBRARY}
+    ${LIB_DL}
+    ${OS_LINK_LIBRARIES}
+)
+
+add_executable(test_native_mini_dfs
+    test_native_mini_dfs.c
+)
+target_link_libraries(test_native_mini_dfs
+    native_mini_dfs
+)
+
+add_executable(test_libhdfs_threaded
+    expect.c
+    test_libhdfs_threaded.c
+    ${OS_DIR}/thread.c
+)
+target_link_libraries(test_libhdfs_threaded
+    hdfs_static
+    native_mini_dfs
+    ${OS_LINK_LIBRARIES}
+)
+
+add_executable(test_libhdfs_zerocopy
+    expect.c
+    test/test_libhdfs_zerocopy.c
+)
+target_link_libraries(test_libhdfs_zerocopy
+    hdfs_static
+    native_mini_dfs
+    ${OS_LINK_LIBRARIES}
+)
+
+add_executable(test_htable
+    common/htable.c
+    test/test_htable.c
+)
+target_link_libraries(test_htable
+    ${OS_LINK_LIBRARIES}
+)
+
+# Skip vecsum on Windows.  This could be made to work in the future by
+# introducing an abstraction layer over the sys/mman.h functions.
+if(NOT WIN32)
+    add_executable(test_libhdfs_vecsum test/vecsum.c)
+    if(CMAKE_SYSTEM_NAME MATCHES "Darwin")
+        target_link_libraries(test_libhdfs_vecsum
+            hdfs
+            pthread)
+    else()
+        target_link_libraries(test_libhdfs_vecsum
+            hdfs
+            pthread
+            rt)
+    endif()
+endif()


Mime
View raw message