def __compactify_remove_index_async( cls, volume_id, parent_id, dead_file_id, dead_dir_index ):
    """
    Remove a freed index slot's node data.
    """
    idx_key_name = MSEntryDirEntIndex.make_key_name( volume_id, parent_id, dead_dir_index )
    ent_key_name = MSEntryEntDirIndex.make_key_name( volume_id, dead_file_id )
    
    idx_key = storagetypes.make_key( MSEntryDirEntIndex, idx_key_name )
    ent_key = storagetypes.make_key( MSEntryEntDirIndex, ent_key_name )
    
    @storagetypes.concurrent
    def delete_index_if_unallocated():
       
       idx_node = yield idx_key.get_async( use_cache=False, use_memcache=False )
       
       if idx_node is None:
           # already gone
           storagetypes.concurrent_return( 0 )
       
       if not idx_node.alloced:
          
          yield idx_key.delete_async()
       
       storagetypes.concurrent_return( 0 )
    
    yield ent_key.delete_async(), storagetypes.transaction_async( delete_index_if_unallocated )
    
    storagetypes.memcache.delete_multi( [idx_key_name, ent_key_name] )

 def delete_volume_and_friends( cls, volume_id, volume_name ):
    """
    Delete the following for a particular volume, as a deferred task:
       the Volume
       # all Volume access requests 
       the Volume name holder
       
    Does not delete attached gateways.
    """
    
    futs = []
    
    # delete volume 
    volume_key = storagetypes.make_key( Volume, Volume.make_key_name( volume_id=volume_id ) )
    futs.append( volume_key.delete_async() )
    
    # delete volume nameholder
    volume_nameholder_key = storagetypes.make_key( VolumeNameHolder, VolumeNameHolder.make_key_name( volume_name ) )
    futs.append( volume_nameholder_key.delete_async() )
    
    # delete volume access requests 
    #volume_access_requests_fut = VolumeAccessRequest.DeleteAccessRequestsByVolume( volume_id, async=True )
    #futs.append( volume_access_requests_fut )
    
    storagetypes.wait_futures( futs )

   def Delete( cls, cls_name_or_id ):
      """
      Given a closure ID, delete the corresponding closure.
      NOTE: Make sure that no gateway references this closure first.
      """
      
      closure = Closure.Read( cls_name_or_id )
      if closure is not None:
         cls_id = closure.closure_id 
      else:
         raise Exception("No such Closure '%s'" % cls_name_or_id )
      
      key_name = Closure.make_key_name( closure_id=cls_id )

      cls_key = storagetypes.make_key( cls, key_name )
      cls_name_key = storagetypes.make_key( ClosureNameHolder, ClosureNameHolder.make_key_name( closure.name ) )
      
      cls_delete_fut = cls_key.delete_async()
      cls_name_delete_fut = cls_name_key.delete_async()
            
      Closure.FlushCache( cls_id )
      
      cls_name_to_id_cache_key = Closure.Read_ByName_name_cache_key( cls_name_or_id )
      storagetypes.memcache.delete( cls_name_to_id_cache_key )
      
      storagetypes.wait_futures( [cls_delete_fut, cls_name_delete_fut] )
      
      return True

 def Delete( cls, g_name_or_id ):
    """
    Given a gateway ID, delete the corresponding gateway.
    Unref the driver as well.
    """
    
    gateway = Gateway.Read( g_name_or_id )
    if gateway:
       g_id = gateway.g_id 
    else:
       raise Exception("No such Gateway '%s'" % g_name_or_id )
    
    key_name = Gateway.make_key_name( g_id=g_id )
    
    g_key = storagetypes.make_key( cls, key_name )
    g_name_key = storagetypes.make_key( GatewayNameHolder, GatewayNameHolder.make_key_name( gateway.name ) )
    
    g_delete_fut = g_key.delete_async()
    g_name_delete_fut = g_name_key.delete_async()
    driver_fut = GatewayDriver.unref_async( gateway.driver_hash )
    
    storagetypes.wait_futures( [g_delete_fut, g_name_delete_fut, driver_fut] )
    
    Gateway.FlushCache( g_id )
    Gateway.FlushCacheDriver( gateway.driver_hash )
    
    g_name_to_id_cache_key = Gateway.Read_ByName_name_cache_key( g_name_or_id )
    storagetypes.memcache.delete( g_name_to_id_cache_key )
    
    return True

 def __update_index_node_async( cls, volume_id, parent_id, file_id, dir_index, alloced, **attrs ):
    """
    Set the allocation status of a directory index node (but not its matching entry index node).
    
    Return 0 on success
    Return -EINVAL if the given file_id doesn't match the directory index node's file_id 
    Return -EEXIST if the given directory index node's allocation status is the same as alloced
    """
    
    index_key_name = MSEntryDirEntIndex.make_key_name( volume_id, parent_id, dir_index )
    index_key = storagetypes.make_key( MSEntryDirEntIndex, index_key_name )
    old_alloced = None
    
    idx = yield index_key.get_async()
    
    if idx is None:
       old_alloced = alloced
       idx = MSEntryDirEntIndex( key=index_key, volume_id=volume_id, parent_id=parent_id, file_id=file_id, dir_index=dir_index, alloced=alloced, **attrs )
    
    else:
       if idx.file_id != file_id:
          # wrong node
          storagetypes.concurrent_return( -errno.EINVAL )
       
       old_alloced = idx.alloced
    
    if old_alloced != alloced:
       # changing allocation status
       idx.populate( -1, volume_id=volume_id, parent_id=parent_id, file_id=file_id, dir_index=dir_index, alloced=alloced, **attrs )
       yield idx.put_async()
    
       storagetypes.concurrent_return( 0 )
    
    else:
       storagetypes.concurrent_return( -errno.EEXIST )

 def put_txn():
    
    volume_cert_bundle = cls.Get( volume_id )
    if volume_cert_bundle is not None:
    
       existing_cert = cls.Load( volume_cert_bundle )
       
       if existing_cert.volume_id != volume_id:
          raise Exception("BUG: existing cert bundle is for %s, but expected %s" % (volume_id, existing_cert.volume_id))
       
       if existing_cert.file_version > cert.file_version:
          raise Exception("Stale volume cert version: expected >= %s, got %s" % (existing_cert.file_version, cert.file_version))
       
       if existing_cert.mtime_sec > cert.mtime_sec or (existing_cert.mtime_sec == cert.mtime_sec and existing_cert.mtime_nsec > cert.mtime_nsec):
          # stale 
          raise Exception("Stale cert bundle timestamp: expected > %s.%s, got %s.%s" % (volume_id, existing_cert.mtime_sec, existing_cert.mtime_nsec, cert.mtime_sec, cert.mtime_nsec))
       
       volume_cert_bundle.cert_protobuf = cert_protobuf
       volume_cert_bundle.put()
       
       storagetypes.memcache.delete( VolumeCertBundle.make_key_name( volume_id ) )
    
    else:
       volume_cert_bundle = VolumeCertBundle( key=storagetypes.make_key( VolumeCertBundle, VolumeCertBundle.make_key_name( volume_id ) ), volume_id=volume_id, cert_protobuf=cert_protobuf )
       volume_cert_bundle.put()
    
    return True 

 def Delete( cls, email ):
    '''
    Delete a SyndicateUser
    
    Arguments:
    email             -- Email of the user to delete (str)
    '''
    
    # can't delete the original admin account 
    if email == ADMIN_EMAIL:
       raise Exception("Cannot delete Syndicate owner")
    
    user_key_name = SyndicateUser.make_key_name( email=email)
    user_key = storagetypes.make_key( SyndicateUser, user_key_name )
    
    def delete_func( user_key ):
       
       user = user_key.get()
    
       if user == None:
          # done!
          return True
       
       user_key.delete()
       return
    
    user_key.delete()
    storagetypes.memcache.delete( user_key_name )
    return True

 def __update_or_alloc_async( cls, volume_id, parent_id, file_id, dir_index, generation, alloced ):
    """
    Update or allocate the index node pair and/or set the directory index node's allocation status, asynchronously.
    If the directory index node does not exist, it and its entry index node will be created and the allocation status set accordingly.
    If the directory index node exists, but has a different allocation status, then the allocation status will be set accordingly.
    
    If we succeed in allocating a new index node, incremenet the number of children in the parent directory.
    
    Return True on success.
    Return False if the index node existed, but the file_id did not match its record or the allocation status did not change.
    """
    
    index_key_name = MSEntryDirEntIndex.make_key_name( volume_id, parent_id, dir_index )
    
    nonce = random.randint( -2**63, 2**63 - 1 )
    result = True
    idx = yield MSEntryDirEntIndex.get_or_insert_async( index_key_name, volume_id=volume_id, parent_id=parent_id, file_id=file_id, dir_index=dir_index, generation=generation, alloced=alloced, nonce=nonce )
    
    if idx.nonce == nonce:
       # created.
       if alloced:
          logging.info("Directory /%s/%s: allocated index slot for /%s/%s at %s" % (volume_id, parent_id, volume_id, file_id, dir_index))
       else:
          logging.info("Directory /%s/%s: freed index slot at %s" % (volume_id, parent_id, dir_index))
       
       # need to create an entry index node as well.
       entry_key_name = MSEntryEntDirIndex.make_key_name( volume_id, file_id )
       entry_key = storagetypes.make_key( MSEntryEntDirIndex, entry_key_name )
       entry_idx = MSEntryEntDirIndex( key=entry_key, volume_id=volume_id, parent_id=parent_id, file_id=file_id, dir_index=dir_index, generation=generation, alloced=alloced, nonce=nonce )
       
       yield entry_idx.put_async()
       
    else:
       
       # already exists.  changing allocation status?
       if idx.alloced != alloced:
          # allocation status needs to be changed
          # want to change allocation status
          rc = yield storagetypes.transaction_async( lambda: cls.__update_index_node_async( volume_id, parent_id, file_id, dir_index, alloced, generation=generation ), xg=True )
          
          if rc == 0:
             result = True 
             
          else:
             logging.error("__update_index_node_async(/%s/%s file_id=%s dir_index=%s alloced=%s) rc = %s" % (volume_id, parent_id, file_id, dir_index, alloced, rc ))
             result = False
       
       else:
          
          if alloced and idx.file_id != file_id:
             # collision on insertion
             logging.error("Directory /%s/%s: collision inserting /%s/%s at %s (occupied by /%s/%s)" % (volume_id, parent_id, volume_id, file_id, dir_index, volume_id, idx.file_id))
             result = False
             
          else:
             # created/set correctly
             result = True
    
    storagetypes.concurrent_return( result )

    def get( self ):
        test_key = storagetypes.make_key( MSBaselinePerformanceType, "test_record" )
        rec = MSBaselinePerformanceType( key=test_key, rec_txt=self.test_record )

        rec.put( use_memcache=False, use_cache=False, use_datastore=True )
        out_rec = test_key.get( use_memcache=False, use_cache=False, use_datastore=True )
        response_end( self, 200, "OK", "text/plain" )
        return

 def update_shard_count( cls, volume_id, num_shards, **txn_args ):
    """
    Update the shard count of the volume, but in a transaction.
    """
    volume_key = storagetypes.make_key( Volume, Volume.make_key_name( volume_id=volume_id ) )      
    num_shards = storagetypes.transaction( lambda: Volume.__update_shard_count( volume_key, num_shards ), **txn_args )
    
    return num_shards

      def set_deleted():
          # atomically set the gateway to deleted
          g_key = storagetypes.make_key( cls, key_name )
          gw = g_key.get()
          if gw is None:
              return None

          gw.deleted = True
          gw.put()
          return gw.key 

 def CreateAdmin( cls, email, openid_url, signing_public_key, activate_password ):
    """
    Create the Admin user.  NOTE: this will be called repeatedly, so use memcache
    """
    
    user_key_name = SyndicateUser.make_key_name( email=email )
    user = storagetypes.memcache.get( user_key_name )
    
    if user == None:
       user_key = storagetypes.make_key( SyndicateUser, user_key_name )
       user = user_key.get()
       
       if user == None:
          # admin does not exist
          attrs = {}
          
          logging.info("Generating admin '%s'" % email)
          
          # fill defaults
          SyndicateUser.fill_defaults( attrs )
          
          attrs['email'] = email
          attrs['openid_url'] = openid_url
          attrs['owner_id'] = random.randint( 1, 2**63 - 1 )
          attrs['is_admin'] = True
          
          # generate password hash and salt
          import common.api as api
          pw_salt = api.password_salt()
          pw_hash = api.hash_password( activate_password, pw_salt )
          
          attrs['activate_password_hash'] = pw_hash
          attrs['activate_password_salt'] = pw_salt
          
          # possible that we haven't set the public key yet
          if not signing_public_key or len(signing_public_key) == 0:
             signing_public_key = cls.USER_KEY_UNSET
             
          attrs['signing_public_key'] = signing_public_key
          
          invalid = SyndicateUser.validate_fields( attrs )
          if len(invalid) != 0:
             raise Exception( "Invalid values for fields: %s" % (", ".join( invalid )))
       
          user = SyndicateUser.get_or_insert( user_key_name, **attrs )
       
          # check for collisions
          if user.owner_id != attrs['owner_id']:
             # collision
             logging.warning("Admin '%s' already exists" % email)
       
       storagetypes.memcache.set( user_key_name, user )
       
    return user.key

 def Delete( cls, volume_id ):
    """
    Delete a cert bundle
    """
    
    key_name = VolumeCertBundle.make_key_name( volume_id )
    volume_cert_bundle_key = storagetypes.make_key( VolumeCertBundle, key_name )
    volume_cert_bundle_key.delete()
    
    storagetypes.memcache.delete( key_name )
    return True 

 def RemoveAccessRequest( cls, owner_id, volume_id ):
    """
    Delete an access request.
    """
    
    req_key_name = VolumeAccessRequest.make_key_name( owner_id, volume_id )
    req_key = storagetypes.make_key( VolumeAccessRequest, req_key_name )
    storagetypes.deferred.defer( cls.delete_all, [req_key] )
    storagetypes.memcache.delete( req_key_name )
    
    return True

 def Delete( cls, email ):
    """
    Delete a SyndicateUser
    """
    
    user_key_name = SyndicateUser.make_key_name( email=email)
    user_key = storagetypes.make_key( SyndicateUser, user_key_name )
    
    user_key.delete()
    storagetypes.memcache.delete( user_key_name )
    return True

   def Create( cls, user, **kwargs ):
      """
      Create a closure.
      Only do this after the closure binary has been uploaded successfully.
      """
      
      # enforce ownership--make sure the calling user owns this closure
      kwargs['owner_id'] = user.owner_id

      # populate kwargs with default values for missing attrs
      cls.fill_defaults( kwargs )
      
      # sanity check: do we have everything we need?
      missing = cls.find_missing_attrs( kwargs )
      if len(missing) != 0:
         raise Exception( "Missing attributes: %s" % (", ".join( missing )))

      # sanity check: are our fields valid?
      invalid = cls.validate_fields( kwargs )
      if len(invalid) != 0:
         raise Exception( "Invalid values for fields: %s" % (", ".join( invalid )) )
      
      # ID...
      closure_id = random.randint( 0, 2**63 - 1 )
      kwargs['closure_id'] = closure_id
      
      closure_key_name = Closure.make_key_name( closure_id=closure_id )
      closure_key = storagetypes.make_key( cls, closure_key_name )
      
      # create a nameholder and this closure at once---there's a good chance we'll succeed
      closure_nameholder_fut = ClosureNameHolder.create_async( kwargs['name'], closure_id )
      closure_fut = cls.get_or_insert_async( closure_key_name, **kwargs )
      
      # wait for operations to complete
      storagetypes.wait_futures( [closure_nameholder_fut, closure_fut] )
      
      # check for collision...
      closure_nameholder = closure_nameholder_fut.get_result()
      closure = closure_fut.get_result()
      
      if closure_nameholder.closure_id != closure_id:
         # name collision...
         storagetypes.deferred.defer( Closure.delete_all, [closure_key] )
         raise Exception( "Closure '%s' already exists!" % kwargs['name'] )
      
      if closure.closure_id != closure_id:
         # ID collision...
         storagetypes.deferred.defer( Closure.delete_all, [closure_nameholder.key, closure_key] )
         raise Exception( "Closure ID collision.  Please try again." )
      
      # we're good!
      return closure_key

 def ref( cls, driver_hash ):
    """
    Increment reference count.
    Do this in an "outer" transaction (i.e. Gateway.Update)
    """
    dk = storagetypes.make_key( GatewayDriver, cls.make_key_name( driver_hash ) )
    d = dk.get()
    
    if d is None:
       return False 
  
    d.refcount += 1
    d.put()
    return True

 def txn():
     
     dk = storagetypes.make_key( GatewayDriver, GatewayDriver.make_key_name( driver_hash ) )
     d = dk.get()
     f = None 
     
     if d is None:
         d = GatewayDriver( key=dk, driver_hash=driver_hash, driver_text=_text, refcount=1 )
         d.put()
     
     else:
         d.refcount += 1
         d.put()
         
     return d

 def GetAccess( cls, owner_id, volume_id ):
    """
    Get the access status of a user in a Volume.
    """
    
    req_key_name = VolumeAccessRequest.make_key_name( owner_id, volume_id )
    req = storagetypes.memcache.get( req_key_name )
    
    if req != None:
       return req
    
    req_key = storagetypes.make_key( VolumeAccessRequest, req_key_name )
    
    req = req_key.get() 
    if req != None:
       storagetypes.memcache.set( req_key_name, req )
    
    return req

 def unref_async( cls, driver_hash ):
    """
    Unref a driver, asynchronously
    Delete it if its ref count goes non-positive.
    Do this in an "outer" transaction (i.e. Gateway.Delete, Gateway.Update)
    """
    dk = storagetypes.make_key( GatewayDriver, cls.make_key_name( driver_hash ) )
    d = dk.get()
    
    if d is None:
        return True 
    
    d.ref -= 1
    if d.ref <= 0:
        d.delete_async()
    else:
        d.put_async()
        
    return True