2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file fs/gnunet-service-fs_push.c
23 * @brief API to push content from our datastore to other peers
24 * ('anonymous'-content P2P migration)
25 * @author Christian Grothoff
28 #include "gnunet-service-fs.h"
29 #include "gnunet-service-fs_cp.h"
30 #include "gnunet-service-fs_indexing.h"
31 #include "gnunet-service-fs_push.h"
34 #define DEBUG_FS_MIGRATION GNUNET_NO
37 * How long must content remain valid for us to consider it for migration?
38 * If content will expire too soon, there is clearly no point in pushing
39 * it to other peers. This value gives the threshold for migration. Note
40 * that if this value is increased, the migration testcase may need to be
41 * adjusted as well (especially the CONTENT_LIFETIME in fs_test_lib.c).
43 #define MIN_MIGRATION_CONTENT_LIFETIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 30)
47 * Block that is ready for migration to other peers. Actual data is at the end of the block.
49 struct MigrationReadyBlock
53 * This is a doubly-linked list.
55 struct MigrationReadyBlock *next;
58 * This is a doubly-linked list.
60 struct MigrationReadyBlock *prev;
63 * Query for the block.
65 GNUNET_HashCode query;
68 * When does this block expire?
70 struct GNUNET_TIME_Absolute expiration;
73 * Peers we already forwarded this
74 * block to. Zero for empty entries.
76 GNUNET_PEER_Id target_list[MIGRATION_LIST_SIZE];
84 * Number of targets already used.
86 unsigned int used_targets;
91 enum GNUNET_BLOCK_Type type;
96 * Information about a peer waiting for
99 struct MigrationReadyPeer
102 * This is a doubly-linked list.
104 struct MigrationReadyPeer *next;
107 * This is a doubly-linked list.
109 struct MigrationReadyPeer *prev;
114 struct GSF_ConnectedPeer *peer;
117 * Handle for current transmission request,
120 struct GSF_PeerTransmitHandle *th;
123 * Message we are trying to push right now (or NULL)
125 struct PutMessage *msg;
130 * Head of linked list of blocks that can be migrated.
132 static struct MigrationReadyBlock *mig_head;
135 * Tail of linked list of blocks that can be migrated.
137 static struct MigrationReadyBlock *mig_tail;
140 * Head of linked list of peers.
142 static struct MigrationReadyPeer *peer_head;
145 * Tail of linked list of peers.
147 static struct MigrationReadyPeer *peer_tail;
150 * Request to datastore for migration (or NULL).
152 static struct GNUNET_DATASTORE_QueueEntry *mig_qe;
155 * ID of task that collects blocks for migration.
157 static GNUNET_SCHEDULER_TaskIdentifier mig_task;
160 * What is the maximum frequency at which we are allowed to
161 * poll the datastore for migration content?
163 static struct GNUNET_TIME_Relative min_migration_delay;
166 * Size of the doubly-linked list of migration blocks.
168 static unsigned int mig_size;
171 * Is this module enabled?
177 * Delete the given migration block.
179 * @param mb block to delete
182 delete_migration_block (struct MigrationReadyBlock *mb)
184 GNUNET_CONTAINER_DLL_remove (mig_head, mig_tail, mb);
185 GNUNET_PEER_decrement_rcs (mb->target_list, MIGRATION_LIST_SIZE);
192 * Find content for migration to this peer.
194 static void find_content (struct MigrationReadyPeer *mrp);
198 * Transmit the message currently scheduled for
201 * @param cls the 'struct MigrationReadyPeer'
202 * @param buf_size number of bytes available in buf
203 * @param buf where to copy the message, NULL on error (peer disconnect)
204 * @return number of bytes copied to 'buf', can be 0 (without indicating an error)
207 transmit_message (void *cls, size_t buf_size, void *buf)
209 struct MigrationReadyPeer *peer = cls;
210 struct PutMessage *msg;
218 #if DEBUG_FS_MIGRATION
219 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
220 "Failed to migrate content to another peer (disconnect)\n");
225 msize = ntohs (msg->header.size);
226 GNUNET_assert (msize <= buf_size);
227 memcpy (buf, msg, msize);
229 #if DEBUG_FS_MIGRATION
230 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Pushing %u bytes to another peer\n",
239 * Send the given block to the given peer.
241 * @param peer target peer
242 * @param block the block
243 * @return GNUNET_YES if the block was deleted (!)
246 transmit_content (struct MigrationReadyPeer *peer,
247 struct MigrationReadyBlock *block)
250 struct PutMessage *msg;
252 struct GSF_PeerPerformanceData *ppd;
255 ppd = GSF_get_peer_performance_data_ (peer->peer);
256 GNUNET_assert (NULL == peer->th);
257 msize = sizeof (struct PutMessage) + block->size;
258 msg = GNUNET_malloc (msize);
259 msg->header.type = htons (GNUNET_MESSAGE_TYPE_FS_PUT);
260 msg->header.size = htons (msize);
261 msg->type = htonl (block->type);
262 msg->expiration = GNUNET_TIME_absolute_hton (block->expiration);
263 memcpy (&msg[1], &block[1], block->size);
265 for (i = 0; i < MIGRATION_LIST_SIZE; i++)
267 if (block->target_list[i] == 0)
269 block->target_list[i] = ppd->pid;
270 GNUNET_PEER_change_rc (block->target_list[i], 1);
274 if (MIGRATION_LIST_SIZE == i)
276 delete_migration_block (block);
283 #if DEBUG_FS_MIGRATION
284 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
285 "Asking for transmission of %u bytes for migration\n", msize);
287 peer->th = GSF_peer_transmit_ (peer->peer, GNUNET_NO, 0 /* priority */ ,
288 GNUNET_TIME_UNIT_FOREVER_REL, msize,
289 &transmit_message, peer);
295 * Count the number of peers this block has
296 * already been forwarded to.
298 * @param block the block
299 * @return number of times block was forwarded
302 count_targets (struct MigrationReadyBlock *block)
306 for (i = 0; i < MIGRATION_LIST_SIZE; i++)
307 if (block->target_list[i] == 0)
314 * Check if sending this block to this peer would
317 * @param peer target peer
318 * @param block the block
319 * @return score (>= 0: feasible, negative: infeasible)
322 score_content (struct MigrationReadyPeer *peer,
323 struct MigrationReadyBlock *block)
326 struct GSF_PeerPerformanceData *ppd;
327 struct GNUNET_PeerIdentity id;
330 ppd = GSF_get_peer_performance_data_ (peer->peer);
331 for (i = 0; i < MIGRATION_LIST_SIZE; i++)
332 if (block->target_list[i] == ppd->pid)
334 GNUNET_assert (0 != ppd->pid);
335 GNUNET_PEER_resolve (ppd->pid, &id);
336 dist = GNUNET_CRYPTO_hash_distance_u32 (&block->query, &id.hashPubKey);
337 /* closer distance, higher score: */
338 return UINT32_MAX - dist;
343 * If the migration task is not currently running, consider
344 * (re)scheduling it with the appropriate delay.
346 static void consider_gathering (void);
350 * Find content for migration to this peer.
352 * @param mrp peer to find content for
355 find_content (struct MigrationReadyPeer *mrp)
357 struct MigrationReadyBlock *pos;
360 struct MigrationReadyBlock *best;
362 GNUNET_assert (NULL == mrp->th);
368 score = score_content (mrp, pos);
369 if (score > best_score)
378 if (mig_size < MAX_MIGRATION_QUEUE)
380 #if DEBUG_FS_MIGRATION
381 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
382 "No content found for pushing, waiting for queue to fill\n");
384 return; /* will fill up eventually... */
386 #if DEBUG_FS_MIGRATION
387 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
388 "No suitable content found, purging content from full queue\n");
390 /* failed to find migration target AND
391 * queue is full, purge most-forwarded
392 * block from queue to make room for more */
396 score = count_targets (pos);
397 if (score >= best_score)
404 GNUNET_assert (NULL != best);
405 delete_migration_block (best);
406 consider_gathering ();
409 #if DEBUG_FS_MIGRATION
410 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
411 "Preparing to push best content to peer\n");
413 transmit_content (mrp, best);
418 * Task that is run periodically to obtain blocks for content
422 * @param tc scheduler context (also unused)
424 static void gather_migration_blocks (void *cls,
425 const struct GNUNET_SCHEDULER_TaskContext
430 * If the migration task is not currently running, consider
431 * (re)scheduling it with the appropriate delay.
434 consider_gathering ()
436 struct GNUNET_TIME_Relative delay;
442 if (mig_task != GNUNET_SCHEDULER_NO_TASK)
444 if (mig_size >= MAX_MIGRATION_QUEUE)
446 delay = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, mig_size);
447 delay = GNUNET_TIME_relative_divide (delay, MAX_MIGRATION_QUEUE);
448 delay = GNUNET_TIME_relative_max (delay, min_migration_delay);
449 #if DEBUG_FS_MIGRATION
450 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
451 "Scheduling gathering task (queue size: %u)\n", mig_size);
454 GNUNET_SCHEDULER_add_delayed (delay, &gather_migration_blocks, NULL);
459 * Process content offered for migration.
462 * @param key key for the content
463 * @param size number of bytes in data
464 * @param data content stored
465 * @param type type of the content
466 * @param priority priority of the content
467 * @param anonymity anonymity-level for the content
468 * @param expiration expiration time for the content
469 * @param uid unique identifier for the datum;
470 * maybe 0 if no unique identifier is available
473 process_migration_content (void *cls, const GNUNET_HashCode * key, size_t size,
474 const void *data, enum GNUNET_BLOCK_Type type,
475 uint32_t priority, uint32_t anonymity,
476 struct GNUNET_TIME_Absolute expiration, uint64_t uid)
478 struct MigrationReadyBlock *mb;
479 struct MigrationReadyPeer *pos;
484 #if DEBUG_FS_MIGRATION
485 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "No content found for migration...\n");
487 consider_gathering ();
490 if (GNUNET_TIME_absolute_get_remaining (expiration).rel_value <
491 MIN_MIGRATION_CONTENT_LIFETIME.rel_value)
493 /* content will expire soon, don't bother */
494 consider_gathering ();
497 if (type == GNUNET_BLOCK_TYPE_FS_ONDEMAND)
500 GNUNET_FS_handle_on_demand_block (key, size, data, type, priority,
501 anonymity, expiration, uid,
502 &process_migration_content, NULL))
503 consider_gathering ();
506 #if DEBUG_FS_MIGRATION
507 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
508 "Retrieved block `%s' of type %u for migration (queue size: %u/%u)\n",
509 GNUNET_h2s (key), type, mig_size + 1, MAX_MIGRATION_QUEUE);
511 mb = GNUNET_malloc (sizeof (struct MigrationReadyBlock) + size);
513 mb->expiration = expiration;
516 memcpy (&mb[1], data, size);
517 GNUNET_CONTAINER_DLL_insert_after (mig_head, mig_tail, mig_tail, mb);
524 #if DEBUG_FS_MIGRATION
525 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
526 "Preparing to push best content to peer\n");
528 if (GNUNET_YES == transmit_content (pos, mb))
529 break; /* 'mb' was freed! */
533 consider_gathering ();
538 * Task that is run periodically to obtain blocks for content
542 * @param tc scheduler context (also unused)
545 gather_migration_blocks (void *cls,
546 const struct GNUNET_SCHEDULER_TaskContext *tc)
548 mig_task = GNUNET_SCHEDULER_NO_TASK;
549 if (mig_size >= MAX_MIGRATION_QUEUE)
553 #if DEBUG_FS_MIGRATION
554 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
555 "Asking datastore for content for replication (queue size: %u)\n",
559 GNUNET_DATASTORE_get_for_replication (GSF_dsh, 0, UINT_MAX,
560 GNUNET_TIME_UNIT_FOREVER_REL,
561 &process_migration_content, NULL);
563 consider_gathering ();
569 * A peer connected to us. Start pushing content
572 * @param peer handle for the peer that connected
575 GSF_push_start_ (struct GSF_ConnectedPeer *peer)
577 struct MigrationReadyPeer *mrp;
579 if (GNUNET_YES != enabled)
581 mrp = GNUNET_malloc (sizeof (struct MigrationReadyPeer));
584 GNUNET_CONTAINER_DLL_insert (peer_head, peer_tail, mrp);
589 * A peer disconnected from us. Stop pushing content
592 * @param peer handle for the peer that disconnected
595 GSF_push_stop_ (struct GSF_ConnectedPeer *peer)
597 struct MigrationReadyPeer *pos;
602 if (pos->peer == peer)
604 GNUNET_CONTAINER_DLL_remove (peer_head, peer_tail, pos);
607 GSF_peer_transmit_cancel_ (pos->th);
610 if (NULL != pos->msg)
612 GNUNET_free (pos->msg);
630 GNUNET_CONFIGURATION_get_value_yesno (GSF_cfg, "FS", "CONTENT_PUSHING");
631 if (GNUNET_YES != enabled)
635 GNUNET_CONFIGURATION_get_value_time (GSF_cfg, "fs", "MIN_MIGRATION_DELAY",
636 &min_migration_delay))
638 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
640 ("Invalid value specified for option `%s' in section `%s', content pushing disabled\n"),
641 "MIN_MIGRATION_DELAY", "fs");
644 consider_gathering ();
649 * Shutdown the module.
654 if (GNUNET_SCHEDULER_NO_TASK != mig_task)
656 GNUNET_SCHEDULER_cancel (mig_task);
657 mig_task = GNUNET_SCHEDULER_NO_TASK;
661 GNUNET_DATASTORE_cancel (mig_qe);
664 while (NULL != mig_head)
665 delete_migration_block (mig_head);
666 GNUNET_assert (0 == mig_size);
669 /* end of gnunet-service-fs_push.c */