work in progress: fix set bug, implement lazy copy

6 files changed, 643 insertions, 114 deletions

diff --git a/src/set/gnunet-service-set.c b/src/set/gnunet-service-set.c
index f2c5c4322..b2ad01d1b 100644
--- a/src/set/gnunet-service-set.c
+++ b/src/set/gnunet-service-set.c
@@ -72,6 +72,16 @@ struct Listener
 };
 
 
+struct LazyCopyRequest
+{
+  struct Set *source_set;
+  uint32_t cookie;
+
+  struct LazyCopyRequest *prev;
+  struct LazyCopyRequest *next;
+};
+
+
 /**
  * Configuration of our local peer.
  */
@@ -115,6 +125,11 @@ static struct Operation *incoming_head;
  */
 static struct Operation *incoming_tail;
 
+static struct LazyCopyRequest *lazy_copy_head;
+static struct LazyCopyRequest *lazy_copy_tail;
+
+static uint32_t lazy_copy_cookie = 1;
+
 /**
  * Counter for allocating unique IDs for clients, used to identify
  * incoming operation requests from remote peers, that the client can
@@ -253,20 +268,20 @@ garbage_collect_cb (void *cls,
                     const struct GNUNET_HashCode *key,
                     void *value)
 {
-  struct GarbageContext *gc = cls;
-  struct ElementEntry *ee = value;
-
-  if (GNUNET_YES != ee->removed)
-    return GNUNET_OK;
-  if ( (gc->max_op_generation < ee->generation_added) ||
-       (ee->generation_removed > gc->min_op_generation) )
-  {
-    GNUNET_assert (GNUNET_YES ==
-                   GNUNET_CONTAINER_multihashmap_remove (gc->map,
-                                                         key,
-                                                         ee));
-    GNUNET_free (ee);
-  }
+  //struct GarbageContext *gc = cls;
+  //struct ElementEntry *ee = value;
+
+  //if (GNUNET_YES != ee->removed)
+  //  return GNUNET_OK;
+  //if ( (gc->max_op_generation < ee->generation_added) ||
+  //     (ee->generation_removed > gc->min_op_generation) )
+  //{
+  //  GNUNET_assert (GNUNET_YES ==
+  //                 GNUNET_CONTAINER_multihashmap_remove (gc->map,
+  //                                                       key,
+  //                                                       ee));
+  //  GNUNET_free (ee);
+  //}
   return GNUNET_OK;
 }
 
@@ -293,12 +308,91 @@ collect_generation_garbage (struct Set *set)
     gc.max_op_generation = GNUNET_MAX (gc.max_op_generation,
                                        op->generation_created);
   }
-  gc.map = set->elements;
-  GNUNET_CONTAINER_multihashmap_iterate (set->elements,
+  gc.map = set->content->elements;
+  GNUNET_CONTAINER_multihashmap_iterate (set->content->elements,
                                          &garbage_collect_cb,
                                          &gc);
 }
 
+int
+is_excluded_generation (unsigned int generation,
+                        struct GenerationRange *excluded,
+                        unsigned int excluded_size)
+{
+  unsigned int i;
+
+  for (i = 0; i < excluded_size; i++)
+  {
+    if ( (generation >= excluded[i].start) && (generation < excluded[i].end) )
+      return GNUNET_YES;
+  }
+
+  return GNUNET_NO;
+}
+
+
+int
+is_element_of_generation (struct ElementEntry *ee,
+                          unsigned int query_generation,
+                          struct GenerationRange *excluded,
+                          unsigned int excluded_size)
+{
+  struct MutationEvent *mut;
+  int is_present;
+
+  if (NULL == ee->mutations)
+    return GNUNET_YES;
+
+  if (GNUNET_YES == is_excluded_generation (query_generation, excluded, excluded_size))
+  {
+    GNUNET_break (0);
+    return GNUNET_NO;
+  }
+
+  is_present = GNUNET_YES;
+
+  // Could be made faster with binary search, but lists
+  // are small, so why bother.
+  for (mut = ee->mutations; 0 != mut->generation; mut++)
+  {
+    if ( (mut->generation > query_generation) ||
+         (GNUNET_YES == is_excluded_generation (mut->generation, excluded, excluded_size)) )
+    {
+      continue;
+    }
+
+    // This would be an inconsistency in how we manage mutations.
+    if ( (GNUNET_YES == is_present) && (GNUNET_YES == mut->added) )
+      GNUNET_assert (0);
+
+    is_present = mut->added;
+  }
+
+  return GNUNET_YES;
+}
+
+
+int
+_GSS_is_element_of_set (struct ElementEntry *ee,
+                        struct Set *set)
+{
+  return is_element_of_generation (ee,
+                                   set->current_generation,
+                                   set->excluded_generations,
+                                   set->excluded_generations_size);
+}
+
+
+int
+_GSS_is_element_of_operation (struct ElementEntry *ee,
+                              struct Operation *op)
+{
+  return is_element_of_generation (ee,
+                                   op->generation_created,
+                                   op->spec->set->excluded_generations,
+                                   op->spec->set->excluded_generations_size);
+}
+
 
 /**
  * Destroy the given operation.  Call the implementation-specific
@@ -371,6 +465,8 @@ destroy_elements_iterator (void *cls,
 {
   struct ElementEntry *ee = value;
 
+  GNUNET_free_non_null (ee->mutations);
+
   GNUNET_free (ee);
   return GNUNET_YES;
 }
@@ -412,17 +508,31 @@ set_destroy (struct Set *set)
     set->iter = NULL;
     set->iteration_id++;
   }
-  if (NULL != set->elements)
   {
-    GNUNET_CONTAINER_multihashmap_iterate (set->elements,
-                                           &destroy_elements_iterator,
-                                           NULL);
-    GNUNET_CONTAINER_multihashmap_destroy (set->elements);
-    set->elements = NULL;
+    struct SetContent *content;
+
+    content = set->content;
+    set->content = NULL;
+    GNUNET_assert (0 != content->refcount);
+    content->refcount -= 1;
+    if (0 == content->refcount)
+    {
+      GNUNET_assert (NULL != content->elements);
+      GNUNET_CONTAINER_multihashmap_iterate (content->elements,
+                                             &destroy_elements_iterator,
+                                             NULL);
+      GNUNET_CONTAINER_multihashmap_destroy (content->elements);
+      content->elements = NULL;
+    }
   }
+  GNUNET_free_non_null (set->excluded_generations);
+  set->excluded_generations = NULL;
   GNUNET_CONTAINER_DLL_remove (sets_head,
                                sets_tail,
                                set);
+
+  // FIXME: remove from lazy copy requests
+
   GNUNET_free (set);
 }
 
@@ -722,10 +832,10 @@ handle_client_iterate (void *cls,
   }
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "Iterating set with %u elements\n",
-              GNUNET_CONTAINER_multihashmap_size (set->elements));
+              GNUNET_CONTAINER_multihashmap_size (set->content->elements));
   GNUNET_SERVER_receive_done (client,
                               GNUNET_OK);
-  set->iter = GNUNET_CONTAINER_multihashmap_iterator_create (set->elements);
+  set->iter = GNUNET_CONTAINER_multihashmap_iterator_create (set->content->elements);
   send_client_element (set);
 }
 
@@ -773,8 +883,11 @@ handle_client_create_set (void *cls,
     GNUNET_SERVER_client_disconnect (client);
     return;
   }
+  set->operation = ntohl (msg->operation);
   set->state = set->vt->create ();
-  set->elements = GNUNET_CONTAINER_multihashmap_create (1, GNUNET_YES);
+  set->content = GNUNET_new (struct SetContent);
+  set->content->refcount = 1;
+  set->content->elements = GNUNET_CONTAINER_multihashmap_create (1, GNUNET_YES);
   set->client = client;
   set->client_mq = GNUNET_MQ_queue_for_server_client (client);
   GNUNET_CONTAINER_DLL_insert (sets_head,
@@ -895,7 +1008,7 @@ handle_client_add (void *cls,
   const struct GNUNET_SET_ElementMessage *msg;
   struct GNUNET_SET_Element el;
   struct ElementEntry *ee;
-  struct ElementEntry *ee_dup;
+  struct GNUNET_HashCode hash;
 
   set = set_get (client);
   if (NULL == set)
@@ -913,28 +1026,43 @@ handle_client_add (void *cls,
               "Client inserts element of size %u\n",
               el.size);
   el.data = &msg[1];
-  ee = GNUNET_malloc (el.size + sizeof *ee);
-  ee->element.size = el.size;
-  memcpy (&ee[1],
-          el.data,
-          el.size);
-  ee->element.data = &ee[1];
-  ee->generation_added = set->current_generation;
-  ee->remote = GNUNET_NO;
-  GNUNET_CRYPTO_hash (ee->element.data,
+  GNUNET_CRYPTO_hash (el.data,
                       el.size,
-                      &ee->element_hash);
-  ee_dup = GNUNET_CONTAINER_multihashmap_get (set->elements,
-                                              &ee->element_hash);
-  if (NULL != ee_dup)
+                      &hash);
+
+  ee = GNUNET_CONTAINER_multihashmap_get (set->content->elements,
+                                          &hash);
+
+  if (NULL == ee)
   {
+    ee = GNUNET_malloc (el.size + sizeof *ee);
+    ee->element.size = el.size;
+    memcpy (&ee[1],
+            el.data,
+            el.size);
+    ee->element.data = &ee[1];
+    ee->remote = GNUNET_NO;
+    ee->mutations = NULL;
+    ee->mutations_size = 0;
+    ee->element_hash = hash;
+  } else if (GNUNET_YES == _GSS_is_element_of_set (ee, set)) {
     /* same element inserted twice */
     GNUNET_break (0);
-    GNUNET_free (ee);
     return;
   }
+
+  if (0 != set->current_generation)
+  {
+    struct MutationEvent mut = {
+      .generation = set->current_generation,
+      .added = GNUNET_YES
+    };
+    GNUNET_array_append (ee->mutations, ee->mutations_size, mut);
+    ee->mutations_size += 1;
+  }
+
   GNUNET_break (GNUNET_YES ==
-                GNUNET_CONTAINER_multihashmap_put (set->elements,
+                GNUNET_CONTAINER_multihashmap_put (set->content->elements,
                                                    &ee->element_hash,
                                                    ee,
                                                    GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
@@ -980,7 +1108,7 @@ handle_client_remove (void *cls,
   GNUNET_CRYPTO_hash (el.data,
                       el.size,
                       &hash);
-  ee = GNUNET_CONTAINER_multihashmap_get (set->elements,
+  ee = GNUNET_CONTAINER_multihashmap_get (set->content->elements,
                                           &hash);
   if (NULL == ee)
   {
@@ -988,18 +1116,65 @@ handle_client_remove (void *cls,
     GNUNET_break (0);
     return;
   }
-  if (GNUNET_YES == ee->removed)
+  if (GNUNET_NO == _GSS_is_element_of_set (ee, set))
   {
     /* Client tried to remove element twice */
     GNUNET_break (0);
     return;
   }
-  ee->removed = GNUNET_YES;
-  ee->generation_removed = set->current_generation;
+  else if (0 == set->current_generation)
+  {
+    // If current_generation is 0, then there are no running set operations
+    // or lazy copies, thus we can safely remove the element.
+    (void) GNUNET_CONTAINER_multihashmap_remove_all (set->content->elements, &hash);
+  }
+  else
+  {
+    struct MutationEvent mut = {
+      .generation = set->current_generation,
+      .added = GNUNET_NO
+    };
+    GNUNET_array_append (ee->mutations, ee->mutations_size, mut);
+    ee->mutations_size += 1;
+  }
   set->vt->remove (set->state, ee);
 }
 
 
+
+/**
+ * Advance the current generation of a set,
+ * adding exclusion ranges if necessary.
+ *
+ * @param set the set where we want to advance the generation
+ */
+static void
+advance_generation (struct Set *set)
+{
+  struct GenerationRange r;
+
+  if (set->current_generation == set->content->latest_generation)
+  {
+    set->content->latest_generation += 1;
+    set->current_generation += 1;
+    return;
+  }
+
+  GNUNET_assert (set->current_generation < set->content->latest_generation);
+
+  r.start = set->current_generation + 1;
+  r.end = set->content->latest_generation + 1;
+
+  set->content->latest_generation = r.end;
+  set->current_generation = r.end;
+
+  GNUNET_array_append (set->excluded_generations,
+                       set->excluded_generations_size,
+                       r);
+
+  set->excluded_generations_size += 1;
+}
+
 /**
  * Called when a client wants to initiate a set operation with another
  * peer.  Initiates the CADET connection to the listener and sends the
@@ -1040,7 +1215,12 @@ handle_client_evaluate (void *cls,
   context = GNUNET_MQ_extract_nested_mh (msg);
   op = GNUNET_new (struct Operation);
   op->spec = spec;
-  op->generation_created = set->current_generation++;
+
+  // Advance generation values, so that
+  // mutations won't interfer with the running operation.
+  op->generation_created = set->current_generation;
+  advance_generation (set);
+
   op->vt = set->vt;
   GNUNET_CONTAINER_DLL_insert (set->ops_head,
                                set->ops_tail,
@@ -1109,6 +1289,135 @@ handle_client_iter_ack (void *cls,
 
 /**
  * Handle a request from the client to
+ * copy a set.
+ *
+ * @param cls unused
+ * @param client the client
+ * @param mh the message
+ */
+static void
+handle_client_copy_lazy_prepare (void *cls,
+                                 struct GNUNET_SERVER_Client *client,
+                                 const struct GNUNET_MessageHeader *mh)
+{
+  struct Set *set;
+  struct LazyCopyRequest *cr;
+
+  set = set_get (client);
+  if (NULL == set)
+  {
+    /* client without a set requested an operation */
+    GNUNET_break (0);
+    GNUNET_SERVER_client_disconnect (client);
+    return;
+  }
+
+  cr = GNUNET_new (struct LazyCopyRequest);
+
+  cr->cookie = lazy_copy_cookie;
+  lazy_copy_cookie += 1;
+  cr->source_set = set;
+
+  GNUNET_CONTAINER_DLL_insert (lazy_copy_head,
+                               lazy_copy_tail,
+                               cr);
+  GNUNET_SERVER_receive_done (client,
+                              GNUNET_OK);
+}
+
+
+/**
+ * Handle a request from the client to
+ * connect to a copy of a set.
+ *
+ * @param cls unused
+ * @param client the client
+ * @param mh the message
+ */
+static void
+handle_client_copy_lazy_connect (void *cls,
+                                 struct GNUNET_SERVER_Client *client,
+                                 const struct GNUNET_MessageHeader *mh)
+{
+  struct LazyCopyRequest *cr;
+  const struct GNUNET_SET_CopyLazyConnectMessage *msg =
+      (const struct GNUNET_SET_CopyLazyConnectMessage *) mh;
+  struct Set *set;
+  int found;
+
+  if (NULL != set_get (client))
+  {
+    /* There can only be one set per client */
+    GNUNET_break (0);
+    GNUNET_SERVER_client_disconnect (client);
+    return;
+  }
+
+  found = GNUNET_NO;
+
+  for (cr = lazy_copy_head; NULL != cr; cr = cr->next)
+  {
+    if (cr->cookie == msg->cookie)
+    {
+      found = GNUNET_YES;
+      break;
+    } 
+  }
+
+  if (GNUNET_NO == found)
+  {
+    /* client asked for copy with cookie we don't know */
+    GNUNET_break (0);
+    GNUNET_SERVER_client_disconnect (client);
+    return;
+  }
+
+  GNUNET_CONTAINER_DLL_remove (lazy_copy_head,
+                               lazy_copy_tail,
+                               cr);
+
+  set = GNUNET_new (struct Set);
+
+  switch (cr->source_set->operation)
+  {
+  case GNUNET_SET_OPERATION_INTERSECTION:
+    set->vt = _GSS_intersection_vt ();
+    break;
+  case GNUNET_SET_OPERATION_UNION:
+    set->vt = _GSS_union_vt ();
+    break;
+  default:
+    GNUNET_assert (0);
+    return;
+  }
+
+  if (NULL == set->vt->copy_state) {
+    /* Lazy copy not supported for this set operation */
+    GNUNET_break (0);
+    GNUNET_free (set);
+    GNUNET_free (cr);
+    return;
+  }
+
+  set->operation = cr->source_set->operation;
+  set->state = set->vt->copy_state (set);
+  set->content = cr->source_set->content;
+  set->content->refcount += 1;
+  set->client = client;
+  set->client_mq = GNUNET_MQ_queue_for_server_client (client);
+  GNUNET_CONTAINER_DLL_insert (sets_head,
+                               sets_tail,
+                               set);
+
+  GNUNET_free (cr);
+
+  GNUNET_SERVER_receive_done (client,
+                              GNUNET_OK);
+}
+
+
+/**
+ * Handle a request from the client to
  * cancel a running set operation.
  *
  * @param cls unused
@@ -1226,7 +1535,12 @@ handle_client_accept (void *cls,
                                op);
   op->spec->client_request_id = ntohl (msg->request_id);
   op->spec->result_mode = ntohl (msg->result_mode);
-  op->generation_created = set->current_generation++;
+
+  // Advance generation values, so that
+  // mutations won't interfer with the running operation.
+  op->generation_created = set->current_generation;
+  advance_generation (set);
+
   op->vt = set->vt;
   op->vt->accept (op);
   GNUNET_SERVER_receive_done (client,
@@ -1497,6 +1811,12 @@ run (void *cls,
     { &handle_client_cancel, NULL,
       GNUNET_MESSAGE_TYPE_SET_CANCEL,
       sizeof (struct GNUNET_SET_CancelMessage)},
+    { &handle_client_copy_lazy_prepare, NULL,
+      GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_PREPARE,
+      sizeof (struct GNUNET_MessageHeader)},
+    { &handle_client_copy_lazy_connect, NULL,
+      GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_CONNECT,
+      sizeof (struct GNUNET_SET_CopyLazyConnectMessage)},
     { NULL, NULL, 0, 0}
   };
   static const struct GNUNET_CADET_MessageHandler cadet_handlers[] = {
diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h
index 8d671ac81..d23291c82 100644
--- a/src/set/gnunet-service-set.h
+++ b/src/set/gnunet-service-set.h
@@ -211,6 +211,10 @@ typedef void
 (*CancelImpl) (struct Operation *op);
 
 
+typedef struct SetState *
+(*CopyStateImpl) (struct Set *op);
+
+
 /**
  * Dispatch table for a specific set operation.  Every set operation
  * has to implement the callback in this struct.
@@ -261,6 +265,30 @@ struct SetVT
    * Callback for canceling an operation by its ID.
    */
   CancelImpl cancel;
+
+  CopyStateImpl copy_state;
+};
+
+
+/**
+ * MutationEvent gives information about changes
+ * to an element (removal / addition) in a set content.
+ */
+struct MutationEvent
+{
+  /**
+   * First generation affected by this mutation event.
+   *
+   * If @a generation is 0, this mutation event is a list
+   * sentinel element.
+   */
+  unsigned int generation;
+
+  /**
+   * If @a added is #GNUNET_YES, then this is a
+   * `remove` event, otherwise it is an `add` event.
+   */
+  int added;
 };
 
 
@@ -285,22 +313,17 @@ struct ElementEntry
   struct GNUNET_HashCode element_hash;
 
   /**
-   * Generation the element was added by the client.
-   * Operations of earlier generations will not consider the element.
-   */
-  unsigned int generation_added;
-
-  /**
-   * Generation the element was removed by the client.
-   * Operations of later generations will not consider the element.
-   * Only valid if @e removed is #GNUNET_YES.
+   * If @a mutations is not NULL, it contains
+   * a list of mutations, ordered by increasing generation.
+   * The list is terminated by a sentinel event with `generation`
+   * set to 0.
+   *
+   * If @a mutations is NULL, then this element exists in all generations
+   * of the respective set content this element belongs to.
    */
-  unsigned int generation_removed;
+  struct MutationEvent *mutations;
 
-  /**
-   * #GNUNET_YES if the element has been removed in some generation.
-   */
-  int removed;
+  unsigned int mutations_size;
 
   /**
    * #GNUNET_YES if the element is a remote element, and does not belong
@@ -323,12 +346,12 @@ struct Operation
   const struct SetVT *vt;
 
   /**
-   * Tunnel to the peer.
+   * Channel to the peer.
    */
   struct GNUNET_CADET_Channel *channel;
 
   /**
-   * Message queue for the tunnel.
+   * Message queue for the channel.
    */
   struct GNUNET_MQ_Handle *mq;
 
@@ -366,7 +389,7 @@ struct Operation
    * Timeout task, if the incoming peer has not been accepted
    * after the timeout, it will be disconnected.
    */
-  struct GNUNET_SCHEDULER_Task * timeout_task;
+  struct GNUNET_SCHEDULER_Task *timeout_task;
 
   /**
    * Unique request id for the request from a remote peer, sent to the
@@ -397,6 +420,41 @@ struct Operation
 
 
 /**
+ * SetContent stores the actual set elements,
+ * which may be shared by multiple generations derived
+ * from one set.
+ */
+struct SetContent
+{
+  /**
+   * Number of references to the content.
+   */
+  unsigned int refcount;
+
+  /**
+   * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
+   */
+  struct GNUNET_CONTAINER_MultiHashMap *elements;
+
+  unsigned int latest_generation;
+};
+
+
+struct GenerationRange
+{
+  /**
+   * First generation that is excluded.
+   */
+  unsigned int start;
+
+  /**
+   * Generation after the last excluded generation.
+   */
+  unsigned int end;
+};
+
+
+/**
  * A set that supports a specific operation with other peers.
  */
 struct Set
@@ -444,11 +502,6 @@ struct Set
   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 
   /**
-   * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
-   */
-  struct GNUNET_CONTAINER_MultiHashMap *elements;
-
-  /**
    * Evaluate operations are held in a linked list.
    */
   struct Operation *ops_head;
@@ -460,11 +513,18 @@ struct Set
 
   /**
    * Current generation, that is, number of previously executed
-   * operations on this set
+   * operations and lazy copies on the underlying set content.
    */
   unsigned int current_generation;
 
   /**
+   * List of generations we have to exclude, due to lazy copies.
+   */
+  struct GenerationRange *excluded_generations;
+
+  unsigned int excluded_generations_size;
+
+  /**
    * Type of operation supported for this set
    */
   enum GNUNET_SET_OperationType operation;
@@ -475,6 +535,12 @@ struct Set
    */
   uint16_t iteration_id;
 
+  /**
+   * Content, possibly shared by multiple sets,
+   * and thus reference counted.
+   */
+  struct SetContent *content;
+
 };
 
 
@@ -510,4 +576,13 @@ const struct SetVT *
 _GSS_intersection_vt (void);
 
 
+int
+_GSS_is_element_of_set (struct ElementEntry *ee,
+                        struct Set *set);
+
+int
+_GSS_is_element_of_operation (struct ElementEntry *ee,
+                              struct Operation *op);
+
+
 #endif
diff --git a/src/set/gnunet-service-set_intersection.c b/src/set/gnunet-service-set_intersection.c
index 55e66a229..a6723e019 100644
--- a/src/set/gnunet-service-set_intersection.c
+++ b/src/set/gnunet-service-set_intersection.c
@@ -239,8 +239,7 @@ filtered_map_initialization (void *cls,
               GNUNET_h2s (&ee->element_hash),
               ee->element.size);
 
-  if ( (op->generation_created < ee->generation_removed) &&
-       (op->generation_created >= ee->generation_added) )
+  if (_GSS_is_element_of_operation (ee, op))
   {
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                 "Reduced initialization, not starting with %s:%u (wrong generation)\n",
@@ -617,7 +616,7 @@ process_bf (struct Operation *op)
               op->state->phase,
               op->spec->remote_element_count,
               op->state->my_element_count,
-              GNUNET_CONTAINER_multihashmap_size (op->spec->set->elements));
+              GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements));
   switch (op->state->phase)
   {
   case PHASE_INITIAL:
@@ -631,7 +630,7 @@ process_bf (struct Operation *op)
       = GNUNET_CONTAINER_multihashmap_create (op->spec->remote_element_count,
                                               GNUNET_YES);
     op->state->my_element_count = 0;
-    GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
+    GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
                                            &filtered_map_initialization,
                                            op);
     break;
@@ -786,8 +785,7 @@ initialize_map_unfiltered (void *cls,
   struct ElementEntry *ee = value;
   struct Operation *op = cls;
 
-  if ( (op->generation_created < ee->generation_removed) &&
-       (op->generation_created >= ee->generation_added) )
+  if (_GSS_is_element_of_operation (ee, op))
     return GNUNET_YES; /* element not live in operation's generation */
   GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
                           &ee->element_hash,
@@ -840,7 +838,7 @@ begin_bf_exchange (struct Operation *op)
   op->state->my_elements
     = GNUNET_CONTAINER_multihashmap_create (op->state->my_element_count,
                                             GNUNET_YES);
-  GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
+  GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
                                          &initialize_map_unfiltered,
                                          op);
   send_bloomfilter (op);
diff --git a/src/set/gnunet-service-set_union.c b/src/set/gnunet-service-set_union.c
index b088ff634..b09e9d2a6 100644
--- a/src/set/gnunet-service-set_union.c
+++ b/src/set/gnunet-service-set_union.c
@@ -515,18 +515,16 @@ init_key_to_element_iterator (void *cls,
                               void *value)
 {
   struct Operation *op = cls;
-  struct ElementEntry *e = value;
+  struct ElementEntry *ee = value;
 
   /* make sure that the element belongs to the set at the time
    * of creating the operation */
-  if ( (e->generation_added > op->generation_created) ||
-       ( (GNUNET_YES == e->removed) &&
-         (e->generation_removed < op->generation_created)))
+  if (GNUNET_NO == _GSS_is_element_of_operation (ee, op))
     return GNUNET_YES;
 
-  GNUNET_assert (GNUNET_NO == e->remote);
+  GNUNET_assert (GNUNET_NO == ee->remote);
 
-  op_register_element (op, e);
+  op_register_element (op, ee);
   return GNUNET_YES;
 }
 
@@ -546,9 +544,9 @@ prepare_ibf (struct Operation *op,
   {
     unsigned int len;
 
-    len = GNUNET_CONTAINER_multihashmap_size (op->spec->set->elements);
+    len = GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements);
     op->state->key_to_element = GNUNET_CONTAINER_multihashmap32_create (len + 1);
-    GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
+    GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
                                            init_key_to_element_iterator, op);
   }
   if (NULL != op->state->local_ibf)
diff --git a/src/set/set.h b/src/set/set.h
index b5750ae3a..0dccf2a51 100644
--- a/src/set/set.h
+++ b/src/set/set.h
@@ -308,6 +308,41 @@ struct GNUNET_SET_IterAckMessage
   uint32_t send_more;
 };
 
+
+/**
+ * Server responds to a lazy copy request.
+ */
+struct GNUNET_SET_CopyLazyResponseMessage
+{
+  /**
+   * Type: #GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_RESPONSE
+   */
+  struct GNUNET_MessageHeader header;
+
+  /**
+   * Temporary name for the copied set.
+   */
+  uint32_t cookie;
+};
+
+
+/**
+ * Client connects to a lazily copied set.
+ */
+struct GNUNET_SET_CopyLazyConnectMessage
+{
+  /**
+   * Type: #GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_CONNECT
+   */
+  struct GNUNET_MessageHeader header;
+
+  /**
+   * Temporary name for the copied set.
+   */
+  uint32_t cookie;
+};
+
+
 GNUNET_NETWORK_STRUCT_END
 
 #endif
diff --git a/src/set/set_api.c b/src/set/set_api.c
index 04ae019d0..aadc93678 100644
--- a/src/set/set_api.c
+++ b/src/set/set_api.c
@@ -33,6 +33,17 @@
 
 #define LOG(kind,...) GNUNET_log_from (kind, "set-api",__VA_ARGS__)
 
+struct SetCopyRequest
+{
+  struct SetCopyRequest *next;
+
+  struct SetCopyRequest *prev;
+
+  void *cls;
+
+  GNUNET_SET_CopyReadyCallback cb;
+};
+
 /**
  * Opaque handle to a set.
  */
@@ -84,6 +95,21 @@ struct GNUNET_SET_Handle
    * created so far to match replies with iterators.
    */
   uint16_t iteration_id;
+
+  /**
+   * Configuration, needed when creating (lazy) copies.
+   */
+  const struct GNUNET_CONFIGURATION_Handle *cfg;
+
+  /**
+   * Doubly linked list of copy requests.
+   */
+  struct SetCopyRequest *copy_req_head;
+
+  /**
+   * Doubly linked list of copy requests.
+   */
+  struct SetCopyRequest *copy_req_tail;
 };
 
 
@@ -213,6 +239,55 @@ struct GNUNET_SET_ListenHandle
 };
 
 
+/* mutual recursion with handle_copy_lazy */
+static struct GNUNET_SET_Handle *
+create_internal (const struct GNUNET_CONFIGURATION_Handle *cfg,
+                 enum GNUNET_SET_OperationType op,
+                 uint32_t *cookie);
+
+
+/**
+ * Handle element for iteration over the set.  Notifies the
+ * iterator and sends an acknowledgement to the service.
+ *
+ * @param cls the `struct GNUNET_SET_Handle *`
+ * @param mh the message
+ */
+static void
+handle_copy_lazy (void *cls,
+                  const struct GNUNET_MessageHeader *mh)
+{
+  struct GNUNET_SET_CopyLazyResponseMessage *msg;
+  struct GNUNET_SET_Handle *set = cls;
+  struct SetCopyRequest *req;
+  struct GNUNET_SET_Handle *new_set;
+
+  msg = (struct GNUNET_SET_CopyLazyResponseMessage *) mh;
+
+  req = set->copy_req_head;
+
+  if (NULL == req)
+  {
+    /* Service sent us unsolicited lazy copy response */
+    GNUNET_break (0);
+    return;
+  }
+  
+  GNUNET_CONTAINER_DLL_remove (set->copy_req_head,
+                               set->copy_req_tail,
+                               req);
+
+  
+  // We pass none as operation here, since it doesn't matter when
+  // cloning.
+  new_set = create_internal (set->cfg, GNUNET_SET_OPERATION_NONE, &msg->cookie);
+
+  req->cb (req->cls, new_set);
+
+  GNUNET_free (req);
+}
+
+
 /**
  * Handle element for iteration over the set.  Notifies the
  * iterator and sends an acknowledgement to the service.
@@ -455,20 +530,10 @@ handle_client_set_error (void *cls,
 }
 
 
-/**
- * Create an empty set, supporting the specified operation.
- *
- * @param cfg configuration to use for connecting to the
- *        set service
- * @param op operation supported by the set
- *        Note that the operation has to be specified
- *        beforehand, as certain set operations need to maintain
- *        data structures spefific to the operation
- * @return a handle to the set
- */
-struct GNUNET_SET_Handle *
-GNUNET_SET_create (const struct GNUNET_CONFIGURATION_Handle *cfg,
-                   enum GNUNET_SET_OperationType op)
+static struct GNUNET_SET_Handle *
+create_internal (const struct GNUNET_CONFIGURATION_Handle *cfg,
+                 enum GNUNET_SET_OperationType op,
+                 uint32_t *cookie)
 {
   static const struct GNUNET_MQ_MessageHandler mq_handlers[] = {
     { &handle_result,
@@ -480,17 +545,22 @@ GNUNET_SET_create (const struct GNUNET_CONFIGURATION_Handle *cfg,
     { &handle_iter_done,
       GNUNET_MESSAGE_TYPE_SET_ITER_DONE,
       sizeof (struct GNUNET_MessageHeader) },
+    { &handle_copy_lazy,
+      GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_RESPONSE,
+      sizeof (struct GNUNET_SET_CopyLazyResponseMessage) },
     GNUNET_MQ_HANDLERS_END
   };
   struct GNUNET_SET_Handle *set;
   struct GNUNET_MQ_Envelope *mqm;
-  struct GNUNET_SET_CreateMessage *msg;
+  struct GNUNET_SET_CreateMessage *create_msg;
+  struct GNUNET_SET_CopyLazyConnectMessage *copy_msg;
 
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "Creating new set (operation %u)\n",
               op);
   set = GNUNET_new (struct GNUNET_SET_Handle);
   set->client = GNUNET_CLIENT_connect ("set", cfg);
+  set->cfg = cfg;
   if (NULL == set->client)
   {
     GNUNET_free (set);
@@ -501,15 +571,44 @@ GNUNET_SET_create (const struct GNUNET_CONFIGURATION_Handle *cfg,
                                                    &handle_client_set_error,
                                                    set);
   GNUNET_assert (NULL != set->mq);
-  mqm = GNUNET_MQ_msg (msg,
-                       GNUNET_MESSAGE_TYPE_SET_CREATE);
-  msg->operation = htonl (op);
+
+  if (NULL == cookie)
+  {
+    mqm = GNUNET_MQ_msg (create_msg,
+                         GNUNET_MESSAGE_TYPE_SET_CREATE);
+    create_msg->operation = htonl (op);
+  }
+  else
+  {
+    mqm = GNUNET_MQ_msg (copy_msg,
+                         GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_CONNECT);
+    copy_msg->cookie = *cookie;
+  }
   GNUNET_MQ_send (set->mq, mqm);
   return set;
 }
 
 
 /**
+ * Create an empty set, supporting the specified operation.
+ *
+ * @param cfg configuration to use for connecting to the
+ *        set service
+ * @param op operation supported by the set
+ *        Note that the operation has to be specified
+ *        beforehand, as certain set operations need to maintain
+ *        data structures spefific to the operation
+ * @return a handle to the set
+ */
+struct GNUNET_SET_Handle *
+GNUNET_SET_create (const struct GNUNET_CONFIGURATION_Handle *cfg,
+                   enum GNUNET_SET_OperationType op)
+{
+  return create_internal (cfg, op, NULL);
+}
+
+
+/**
  * Add an element to the given set.  After the element has been added
  * (in the sense of being transmitted to the set service), @a cont
  * will be called.  Multiple calls to GNUNET_SET_add_element() can be
@@ -976,19 +1075,23 @@ GNUNET_SET_iterate (struct GNUNET_SET_Handle *set,
 }
 
 
-/**
- * Stop iteration over all elements in the given set.  Can only
- * be called before the iteration has "naturally" completed its
- * turn.
- *
- * @param set the set to stop iterating over
- */
 void
-GNUNET_SET_iterate_cancel (struct GNUNET_SET_Handle *set)
+GNUNET_SET_copy_lazy (struct GNUNET_SET_Handle *set,
+                      GNUNET_SET_CopyReadyCallback cb,
+                      void *cls)
 {
-  GNUNET_assert (NULL != set->iterator);
-  set->iterator = NULL;
-  set->iteration_id++;
+  struct GNUNET_MQ_Envelope *ev;
+  struct SetCopyRequest *req;
+
+  ev = GNUNET_MQ_msg_header (GNUNET_MESSAGE_TYPE_SET_COPY_LAZY_PREPARE);
+  GNUNET_MQ_send (set->mq, ev);
+
+  req = GNUNET_new (struct SetCopyRequest);
+  req->cb = cb;
+  req->cls = cls;
+  GNUNET_CONTAINER_DLL_insert (set->copy_req_head,
+                               set->copy_req_tail,
+                               req);
 }