Use a single lock file for stages and a single file for prefixes.

- Locks now use fcntl range locks on a single file.

How it works for prefixes:

- Each lock is a byte range lock on the nth byte of a file.

- The lock file is ``spack.installed_db.prefix_lock`` -- the DB tells us
  what to call it and it lives alongside the install DB.  n is the
  sys.maxsize-bit prefix of the DAG hash.

For stages, we take the sha1 of the stage name and use that to select a
byte to lock.

With 100 concurrent builds, the likelihood of a false lock collision is
~5.36e-16, so this scheme should retain more than sufficient paralellism
(with no chance of false negatives), and get us reader-writer lock
semantics with a single file, so no need to clean up lots of lock files.

5 files changed, 57 insertions, 18 deletions

diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index 0af08e9449..e9bd07d92c 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -156,6 +156,9 @@ class Database(object):
         self._index_path = join_path(self._db_dir, 'index.yaml')
         self._lock_path = join_path(self._db_dir, 'lock')
 
+        # This is for other classes to use to lock prefix directories.
+        self.prefix_lock_path = join_path(self._db_dir, 'prefix_lock')
+
         # Create needed directories and files
         if not os.path.exists(self._db_dir):
             mkdirp(self._db_dir)
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index 9b1c6b11a2..42e18b2a1e 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -309,6 +309,7 @@ class Package(object):
     Package creators override functions like install() (all of them do this),
     clean() (some of them do this), and others to provide custom behavior.
     """
+
     #
     # These are default values for instance variables.
     #
@@ -340,6 +341,9 @@ class Package(object):
     """
     sanity_check_is_dir = []
 
+    """Per-process lock objects for each install prefix."""
+    prefix_locks = {}
+
     class __metaclass__(type):
         """Ensure  attributes required by Spack directives are present."""
         def __init__(cls, name, bases, dict):
@@ -700,11 +704,24 @@ class Package(object):
 
     @property
     def prefix_lock(self):
+        """Prefix lock is a byte range lock on the nth byte of a file.
+
+        The lock file is ``spack.installed_db.prefix_lock`` -- the DB
+        tells us what to call it and it lives alongside the install DB.
+
+        n is the sys.maxsize-bit prefix of the DAG hash.  This makes
+        likelihood of collision is very low AND it gives us
+        readers-writer lock semantics with just a single lockfile, so no
+        cleanup required.
+        """
         if self._prefix_lock is None:
-            dirname = join_path(os.path.dirname(self.spec.prefix), '.locks')
-            basename = os.path.basename(self.spec.prefix)
-            self._prefix_lock = llnl.util.lock.Lock(
-                join_path(dirname, basename))
+            prefix = self.spec.prefix
+            if prefix not in Package.prefix_locks:
+                Package.prefix_locks[prefix] = llnl.util.lock.Lock(
+                    spack.installed_db.prefix_lock_path,
+                    self.spec.dag_hash_bit_prefix(sys.maxsize.bit_length()), 1)
+
+            self._prefix_lock = Package.prefix_locks[prefix]
 
         return self._prefix_lock
 
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 94ac8788ba..fc4bf41e34 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -120,6 +120,7 @@ from spack.util.prefix import Prefix
 from spack.util.string import *
 import spack.util.spack_yaml as syaml
 from spack.util.spack_yaml import syaml_dict
+from spack.util.crypto import prefix_bits
 from spack.version import *
 from spack.provider_index import ProviderIndex
 
@@ -2733,17 +2734,7 @@ def base32_prefix_bits(hash_string, bits):
                          % (bits, hash_string))
 
     hash_bytes = base64.b32decode(hash_string, casefold=True)
-
-    result = 0
-    n = 0
-    for i, b in enumerate(hash_bytes):
-        n += 8
-        result = (result << 8) | ord(b)
-        if n >= bits:
-            break
-
-    result >>= (n - bits)
-    return result
+    return prefix_bits(hash_bytes, bits)
 
 
 class SpecError(spack.error.SpackError):
diff --git a/lib/spack/spack/stage.py b/lib/spack/spack/stage.py
index f282c3e1c0..230defc67e 100644
--- a/lib/spack/spack/stage.py
+++ b/lib/spack/spack/stage.py
@@ -23,7 +23,9 @@
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
 import os
+import sys
 import errno
+import hashlib
 import shutil
 import tempfile
 from urlparse import urljoin
@@ -39,6 +41,7 @@ import spack.config
 import spack.fetch_strategy as fs
 import spack.error
 from spack.version import *
+from spack.util.crypto import prefix_bits
 
 STAGE_PREFIX = 'spack-stage-'
 
@@ -89,6 +92,9 @@ class Stage(object):
     similar, and are intended to persist for only one run of spack.
     """
 
+    """Shared dict of all stage locks."""
+    stage_locks = {}
+
     def __init__(
             self, url_or_fetch_strategy,
             name=None, mirror_path=None, keep=False, path=None, lock=True):
@@ -149,11 +155,19 @@ class Stage(object):
         # Flag to decide whether to delete the stage folder on exit or not
         self.keep = keep
 
-        # File lock for the stage directory
+        # File lock for the stage directory.  We use one file for all
+        # stage locks. See Spec.prefix_lock for details on this approach.
         self._lock = None
         if lock:
-            self._lock = llnl.util.lock.Lock(
-                join_path(spack.stage_path, self.name + '.lock'))
+            if self.name not in Stage.stage_locks:
+                sha1 = hashlib.sha1(self.name).digest()
+                lock_id = prefix_bits(sha1, sys.maxsize.bit_length())
+                stage_lock_path = join_path(spack.stage_path, '.lock')
+
+                Stage.stage_locks[self.name] = llnl.util.lock.Lock(
+                    stage_lock_path, lock_id, 1)
+
+            self._lock = Stage.stage_locks[self.name]
 
     def __enter__(self):
         """
diff --git a/lib/spack/spack/util/crypto.py b/lib/spack/spack/util/crypto.py
index 22777fdb68..6e17b74774 100644
--- a/lib/spack/spack/util/crypto.py
+++ b/lib/spack/spack/util/crypto.py
@@ -100,3 +100,17 @@ class Checker(object):
         self.sum = checksum(
             self.hash_fun, filename, block_size=self.block_size)
         return self.sum == self.hexdigest
+
+
+def prefix_bits(byte_array, bits):
+    """Return the first <bits> bits of a byte array as an integer."""
+    result = 0
+    n = 0
+    for i, b in enumerate(byte_array):
+        n += 8
+        result = (result << 8) | ord(b)
+        if n >= bits:
+            break
+
+    result >>= (n - bits)
+    return result