123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673 |
- /*
- This file is part of GNUnet
- Copyright (C) 2013-2017 GNUnet e.V.
- GNUnet is free software: you can redistribute it and/or modify it
- under the terms of the GNU Affero General Public License as published
- by the Free Software Foundation, either version 3 of the License,
- or (at your option) any later version.
- GNUnet is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Affero General Public License for more details.
-
- You should have received a copy of the GNU Affero General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
- SPDX-License-Identifier: AGPL3.0-or-later
- */
- /**
- * @file set/gnunet-service-set.h
- * @brief common components for the implementation the different set operations
- * @author Florian Dold
- * @author Christian Grothoff
- */
- #ifndef GNUNET_SERVICE_SET_H_PRIVATE
- #define GNUNET_SERVICE_SET_H_PRIVATE
- #include "platform.h"
- #include "gnunet_util_lib.h"
- #include "gnunet_protocols.h"
- #include "gnunet_applications.h"
- #include "gnunet_core_service.h"
- #include "gnunet_cadet_service.h"
- #include "gnunet_set_service.h"
- #include "set.h"
- /**
- * Implementation-specific set state. Used as opaque pointer, and
- * specified further in the respective implementation.
- */
- struct SetState;
- /**
- * Implementation-specific set operation. Used as opaque pointer, and
- * specified further in the respective implementation.
- */
- struct OperationState;
- /**
- * A set that supports a specific operation with other peers.
- */
- struct Set;
- /**
- * Information about an element element in the set. All elements are
- * stored in a hash-table from their hash-code to their 'struct
- * Element', so that the remove and add operations are reasonably
- * fast.
- */
- struct ElementEntry;
- /**
- * Operation context used to execute a set operation.
- */
- struct Operation;
- /**
- * Signature of functions that create the implementation-specific
- * state for a set supporting a specific operation.
- *
- * @return a set state specific to the supported operation, NULL on error
- */
- typedef struct SetState *
- (*SetCreateImpl) (void);
- /**
- * Signature of functions that implement the add/remove functionality
- * for a set supporting a specific operation.
- *
- * @param set implementation-specific set state
- * @param ee element message from the client
- */
- typedef void
- (*SetAddRemoveImpl) (struct SetState *state,
- struct ElementEntry *ee);
- /**
- * Make a copy of a set's internal state.
- *
- * @param state set state to copy
- * @return copy of the internal state
- */
- typedef struct SetState *
- (*SetCopyStateImpl) (struct SetState *state);
- /**
- * Signature of functions that implement the destruction of the
- * implementation-specific set state.
- *
- * @param state the set state, contains implementation-specific data
- */
- typedef void
- (*SetDestroyImpl) (struct SetState *state);
- /**
- * Signature of functions that implement accepting a set operation.
- *
- * @param op operation that is created by accepting the operation,
- * should be initialized by the implementation
- * @return operation-specific state to keep in @a op
- */
- typedef struct OperationState *
- (*OpAcceptImpl) (struct Operation *op);
- /**
- * Signature of functions that implement starting the evaluation of
- * set operations.
- *
- * @param op operation that is created, should be initialized to
- * begin the evaluation
- * @param opaque_context message to be transmitted to the listener
- * to convince it to accept, may be NULL
- * @return operation-specific state to keep in @a op
- */
- typedef struct OperationState *
- (*OpEvaluateImpl) (struct Operation *op,
- const struct GNUNET_MessageHeader *opaque_context);
- /**
- * Signature of functions that implement operation cancelation.
- * This includes notifying the client about the operation's final
- * state.
- *
- * @param op operation state
- */
- typedef void
- (*OpCancelImpl) (struct Operation *op);
- /**
- * Signature of functions called when the CADET channel died.
- *
- * @param op operation state
- */
- typedef void
- (*OpChannelDeathImpl) (struct Operation *op);
- /**
- * Dispatch table for a specific set operation. Every set operation
- * has to implement the callback in this struct.
- */
- struct SetVT
- {
- /**
- * Callback for the set creation.
- */
- SetCreateImpl create;
- /**
- * Callback for element insertion
- */
- SetAddRemoveImpl add;
- /**
- * Callback for element removal.
- */
- SetAddRemoveImpl remove;
- /**
- * Callback for making a copy of a set's internal state.
- */
- SetCopyStateImpl copy_state;
- /**
- * Callback for destruction of the set state.
- */
- SetDestroyImpl destroy_set;
- /**
- * Callback for accepting a set operation request
- */
- OpAcceptImpl accept;
- /**
- * Callback for starting evaluation with a remote peer.
- */
- OpEvaluateImpl evaluate;
- /**
- * Callback for canceling an operation.
- */
- OpCancelImpl cancel;
- /**
- * Callback called in case the CADET channel died.
- */
- OpChannelDeathImpl channel_death;
- };
- /**
- * 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;
- };
- /**
- * Information about an element element in the set. All elements are
- * stored in a hash-table from their hash-code to their `struct
- * Element`, so that the remove and add operations are reasonably
- * fast.
- */
- struct ElementEntry
- {
- /**
- * The actual element. The data for the element
- * should be allocated at the end of this struct.
- */
- struct GNUNET_SET_Element element;
- /**
- * Hash of the element. For set union: Will be used to derive the
- * different IBF keys for different salts.
- */
- struct GNUNET_HashCode element_hash;
- /**
- * 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.
- */
- struct MutationEvent *mutations;
- /**
- * Number of elements in the array @a mutations.
- */
- unsigned int mutations_size;
- /**
- * #GNUNET_YES if the element is a remote element, and does not belong
- * to the operation's set.
- */
- int remote;
- };
- /**
- * A listener is inhabited by a client, and waits for evaluation
- * requests from remote peers.
- */
- struct Listener;
- /**
- * State we keep per client.
- */
- struct ClientState
- {
- /**
- * Set, if associated with the client, otherwise NULL.
- */
- struct Set *set;
- /**
- * Listener, if associated with the client, otherwise NULL.
- */
- struct Listener *listener;
- /**
- * Client handle.
- */
- struct GNUNET_SERVICE_Client *client;
- /**
- * Message queue.
- */
- struct GNUNET_MQ_Handle *mq;
- };
- /**
- * Operation context used to execute a set operation.
- */
- struct Operation
- {
- /**
- * Kept in a DLL of the listener, if @e listener is non-NULL.
- */
- struct Operation *next;
- /**
- * Kept in a DLL of the listener, if @e listener is non-NULL.
- */
- struct Operation *prev;
- /**
- * Channel to the peer.
- */
- struct GNUNET_CADET_Channel *channel;
- /**
- * Port this operation runs on.
- */
- struct Listener *listener;
- /**
- * Message queue for the channel.
- */
- struct GNUNET_MQ_Handle *mq;
- /**
- * Context message, may be NULL.
- */
- struct GNUNET_MessageHeader *context_msg;
- /**
- * Set associated with the operation, NULL until the spec has been
- * associated with a set.
- */
- struct Set *set;
- /**
- * Operation-specific operation state. Note that the exact
- * type depends on this being a union or intersection operation
- * (and thus on @e vt).
- */
- struct OperationState *state;
- /**
- * The identity of the requesting peer. Needs to
- * be stored here as the op spec might not have been created yet.
- */
- struct GNUNET_PeerIdentity peer;
- /**
- * Timeout task, if the incoming peer has not been accepted
- * after the timeout, it will be disconnected.
- */
- struct GNUNET_SCHEDULER_Task *timeout_task;
- /**
- * Salt to use for the operation.
- */
- uint32_t salt;
- /**
- * Remote peers element count
- */
- uint32_t remote_element_count;
- /**
- * ID used to identify an operation between service and client
- */
- uint32_t client_request_id;
- /**
- * When are elements sent to the client, and which elements are sent?
- */
- enum GNUNET_SET_ResultMode result_mode;
- /**
- * Always use delta operation instead of sending full sets,
- * even it it's less efficient.
- */
- int force_delta;
- /**
- * Always send full sets, even if delta operations would
- * be more efficient.
- */
- int force_full;
- /**
- * #GNUNET_YES to fail operations where Byzantine faults
- * are suspected
- */
- int byzantine;
- /**
- * Lower bound for the set size, used only when
- * byzantine mode is enabled.
- */
- int byzantine_lower_bound;
- /**
- * Unique request id for the request from a remote peer, sent to the
- * client, which will accept or reject the request. Set to '0' iff
- * the request has not been suggested yet.
- */
- uint32_t suggest_id;
- /**
- * Generation in which the operation handle
- * was created.
- */
- unsigned int generation_created;
- };
- /**
- * SetContent stores the actual set elements, which may be shared by
- * multiple generations derived from one set.
- */
- struct SetContent
- {
- /**
- * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
- */
- struct GNUNET_CONTAINER_MultiHashMap *elements;
- /**
- * Mutations requested by the client that we're
- * unable to execute right now because we're iterating
- * over the underlying hash map of elements.
- */
- struct PendingMutation *pending_mutations_head;
- /**
- * Mutations requested by the client that we're
- * unable to execute right now because we're iterating
- * over the underlying hash map of elements.
- */
- struct PendingMutation *pending_mutations_tail;
- /**
- * Number of references to the content.
- */
- unsigned int refcount;
- /**
- * FIXME: document!
- */
- unsigned int latest_generation;
- /**
- * Number of concurrently active iterators.
- */
- int iterator_count;
- };
- struct GenerationRange
- {
- /**
- * First generation that is excluded.
- */
- unsigned int start;
- /**
- * Generation after the last excluded generation.
- */
- unsigned int end;
- };
- /**
- * Information about a mutation to apply to a set.
- */
- struct PendingMutation
- {
- /**
- * Mutations are kept in a DLL.
- */
- struct PendingMutation *prev;
- /**
- * Mutations are kept in a DLL.
- */
- struct PendingMutation *next;
- /**
- * Set this mutation is about.
- */
- struct Set *set;
- /**
- * Message that describes the desired mutation.
- * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
- * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
- */
- struct GNUNET_SET_ElementMessage *msg;
- };
- /**
- * A set that supports a specific operation with other peers.
- */
- struct Set
- {
- /**
- * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
- */
- struct Set *next;
- /**
- * Sets are held in a doubly linked list.
- */
- struct Set *prev;
- /**
- * Client that owns the set. Only one client may own a set,
- * and there can only be one set per client.
- */
- struct ClientState *cs;
- /**
- * Content, possibly shared by multiple sets,
- * and thus reference counted.
- */
- struct SetContent *content;
- /**
- * Virtual table for this set. Determined by the operation type of
- * this set.
- *
- * Used only for Add/remove of elements and when receiving an incoming
- * operation from a remote peer.
- */
- const struct SetVT *vt;
- /**
- * Implementation-specific state.
- */
- struct SetState *state;
- /**
- * Current state of iterating elements for the client.
- * NULL if we are not currently iterating.
- */
- struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
- /**
- * Evaluate operations are held in a linked list.
- */
- struct Operation *ops_head;
- /**
- * Evaluate operations are held in a linked list.
- */
- struct Operation *ops_tail;
- /**
- * List of generations we have to exclude, due to lazy copies.
- */
- struct GenerationRange *excluded_generations;
- /**
- * Current generation, that is, number of previously executed
- * operations and lazy copies on the underlying set content.
- */
- unsigned int current_generation;
- /**
- * Number of elements in array @a excluded_generations.
- */
- unsigned int excluded_generations_size;
- /**
- * Type of operation supported for this set
- */
- enum GNUNET_SET_OperationType operation;
- /**
- * Generation we're currently iteration over.
- */
- unsigned int iter_generation;
- /**
- * Each @e iter is assigned a unique number, so that the client
- * can distinguish iterations.
- */
- uint16_t iteration_id;
- };
- extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
- /**
- * Destroy the given operation. Used for any operation where both
- * peers were known and that thus actually had a vt and channel. Must
- * not be used for operations where 'listener' is still set and we do
- * not know the other peer.
- *
- * Call the implementation-specific cancel function of the operation.
- * Disconnects from the remote peer. Does not disconnect the client,
- * as there may be multiple operations per set.
- *
- * @param op operation to destroy
- * @param gc #GNUNET_YES to perform garbage collection on the set
- */
- void
- _GSS_operation_destroy (struct Operation *op,
- int gc);
- /**
- * This function probably should not exist
- * and be replaced by inlining more specific
- * logic in the various places where it is called.
- */
- void
- _GSS_operation_destroy2 (struct Operation *op);
- /**
- * Get the table with implementing functions for set union.
- *
- * @return the operation specific VTable
- */
- const struct SetVT *
- _GSS_union_vt (void);
- /**
- * Get the table with implementing functions for set intersection.
- *
- * @return the operation specific VTable
- */
- const struct SetVT *
- _GSS_intersection_vt (void);
- /**
- * Is element @a ee part of the set used by @a op?
- *
- * @param ee element to test
- * @param op operation the defines the set and its generation
- * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
- */
- int
- _GSS_is_element_of_operation (struct ElementEntry *ee,
- struct Operation *op);
- #endif
|