Index: trunk/Nebulous-Server/lib/Nebulous/Server.pm
===================================================================
--- trunk/Nebulous-Server/lib/Nebulous/Server.pm	(revision 24637)
+++ trunk/Nebulous-Server/lib/Nebulous/Server.pm	(revision 24915)
@@ -844,4 +844,99 @@
 
 
+sub prune_object
+{
+    my $self = shift;
+
+    my $log = $self->log;
+    $log->debug("entered - @_");
+
+    my ($key) = validate_pos(@_,
+        {
+            type        => SCALAR,
+            callbacks   => {
+                'is valid object key'
+                    => sub { $self->_is_valid_object_key($_[0]) },
+            },
+        },
+    );
+
+    my $sql = $self->sql;
+
+    eval {
+        $key = parse_neb_key($key);
+    };
+    $log->logdie("$@") if $@;
+
+    my $db  = $self->db($key);
+
+    my $rows_removed = 0;
+TRANS: while (1) {
+        eval {
+            # remove key from cache
+            $self->cache->delete($key->path) if defined $self->cache;
+
+            my $so_id;
+            {
+                my $query = $db->prepare_cached( $sql->find_object_by_ext_id );
+                $query->execute( $key->path );
+                $so_id = $query->fetchrow_hashref->{'so_id'};
+                $query->finish;
+            }
+
+            # record the path of the innaccesible files for deferred
+            # deletion
+            my $rows_copied;
+            {
+                my $query = $db->prepare_cached( $sql->copy_dead_instances_to_deleted );
+                $rows_copied = $query->execute( $so_id );
+            }
+
+            # check to see if there is anything to be done
+            unless ($rows_copied > 0) {
+                $db->rollback;
+                return;
+            }
+
+            # In MySQL you can't select from a table your deleting rows from so
+            # we first have to get a list of instances to be removed, and then
+            # removed them.
+            my $rows_found;
+            {
+                my $query = $db->prepare_cached( $sql->find_dead_instances_by_so_id );
+                $rows_found = $query->execute( $so_id );
+                foreach my $row ($query->fetchrow_hashref) {
+                    # remove dead instances
+                    my $query = $db->prepare_cached( $sql->delete_instance_by_ins_id);
+                    $rows_removed += $query->execute( $row->{ins_id} );
+                }
+                $query->finish;
+            }
+
+            # sanity check
+            die("instances inaccessible ($rows_copied) != instances removed ($rows_removed)")
+                unless $rows_copied == $rows_removed;
+            
+            $db->commit;
+            $log->debug("commit");
+        };
+        if ($@) {
+            $db->rollback;
+            $log->debug("rollback");
+            if ($@ =~ $trans_regex) {
+                $log->warn("database error, retrying transaction: $@");
+                sleep TRANS_RETRY_WAIT;
+                redo TRANS;
+            }
+            $log->logdie("error: $@");
+        }
+        last;
+    }
+
+    $log->debug("leaving");
+
+    return $rows_removed;
+}
+
+
 sub lock_object
 {
@@ -1674,17 +1769,7 @@
                 # remove key from cache
                 $self->cache->delete($key->path) if defined $self->cache;
-
-                # record the path of the innaccesible files for deferred
-                # deletion
-                {
-                    my $query = $db->prepare_cached( $sql->copy_instances_to_deleted );
-                    $query->execute( $so_id );
-                }
-                # remove all instances... not strictly nessicary as the delete
-                # from storage_object should cascade but the fkey was specified
-                # without the cascade 
-                {
-                    my $query = $db->prepare_cached( $sql->delete_instance_by_so_id );
-                    $query->execute( $so_id );
+                
+                if ($total > $available) {
+                    $self->prune_object("$key");
                 }