INN commit: trunk (5 files)

INN Commit Russ_Allbery at isc.org
Thu Mar 20 14:26:13 UTC 2008


    Date: Thursday, March 20, 2008 @ 07:26:12
  Author: iulius
Revision: 7713

Implementation of the Diablo Quickhash algorithm.  It allows
to distribute the messages among several peers (new Q flag
for newsfeeds).

Thanks to Miquel van Smoorenburg for this implementation in INN.

Modified:
  trunk/doc/pod/newsfeeds.pod
  trunk/innd/art.c
  trunk/innd/innd.h
  trunk/innd/newsfeeds.c
  trunk/innd/site.c

-----------------------+
 doc/pod/newsfeeds.pod |   27 +++++++++++++++++++++++++++
 innd/art.c            |   27 +++++++++++++++++++++++++++
 innd/innd.h           |   10 ++++++++++
 innd/newsfeeds.c      |   14 ++++++++++++++
 innd/site.c           |    5 +++++
 5 files changed, 83 insertions(+)

Modified: doc/pod/newsfeeds.pod
===================================================================
--- doc/pod/newsfeeds.pod	2008-02-05 23:21:23 UTC (rev 7712)
+++ doc/pod/newsfeeds.pod	2008-03-20 14:26:12 UTC (rev 7713)
@@ -384,6 +384,33 @@
 new process will run with.  This flag can be used to raise the priority to
 normal if you're using the I<nicekids> parameter in F<inn.conf>.
 
+=item B<Q> I<hashfeed>
+
+Specifies the I<hashfeed> value for this site.  The Message-ID of the
+article is hashed using a quick (but dirty) hash method (31-bits sum
+of the value of all characters).  The I<hashfeed> value must be given
+as C<value/mod> or as C<start-end/mod>.  If the Message-ID hash modulus
+C<mod> plus one equals C<value> or is between C<start> and C<end>,
+the article will be fed to this site.  All these numbers must be integers.
+
+For instance:
+
+    Q1/2      Feeds about 50% of the messages to this site.
+    Q2/2      Feeds the other 50% of the messages.
+
+Another example with three sites:
+
+    Q1-3/10   Feeds about 30% of the messages.
+    Q4-5/10   Feeds about 20% of the messages.
+    Q6-10/10  Feeds about 50% of the messages.
+
+If this flag is specified multiple times, the contents will be
+logically C<OR>ed together (just one matched flag is needed).
+
+The algorithm is compatible with the legacy Quickhash used by Diablo.
+Please note that the distribution of the messages is not perfect with
+this algorithm.
+
 =item B<S> I<size>
 
 If the amount of data queued for the site gets to be larger than I<size>

Modified: innd/art.c
===================================================================
--- innd/art.c	2008-02-05 23:21:23 UTC (rev 7712)
+++ innd/art.c	2008-03-20 14:26:12 UTC (rev 7713)
@@ -1538,6 +1538,29 @@
 }
 
 /*
+**  Return true if an element of the QHASHLIST matches the
+**  quickhash of the Message-ID.
+*/
+static bool
+QHashMatch(QHASHLIST *qh, char *MessageID)
+{
+  unsigned char *p = (unsigned char *)MessageID;
+  int h = 0;
+
+  while (*p)
+    h += *p++;
+
+  while (qh) {
+    if ((h % qh->mod + 1) >= qh->begin &&
+        (h % qh->mod + 1) <= qh->end)
+          return true;
+    qh = qh->next;
+  }
+
+  return false;
+}
+
+/*
 **  Propagate an article to the sites have "expressed an interest."
 */
 static void
@@ -1610,6 +1633,10 @@
        * cross-posting. */
       continue;
 
+    if (sp->QHashList && !QHashMatch(sp->QHashList, HDR(HDR__MESSAGE_ID)))
+      /* Quickhash doesn't match. */
+      continue;
+
     if (list && *list != NULL && sp->Distributions &&
       !DISTwantany(sp->Distributions, list))
       /* Not in the site's desired list of distributions. */

Modified: innd/innd.h
===================================================================
--- innd/innd.h	2008-02-05 23:21:23 UTC (rev 7712)
+++ innd/innd.h	2008-03-20 14:26:12 UTC (rev 7713)
@@ -398,6 +398,15 @@
   FTprogram
 } FEEDTYPE;
 
+/*
+**  Diablo-style hashed feeds or hashfeeds.
+*/
+typedef struct _QHASHLIST {
+  int             begin;
+  int             end;
+  int             mod;
+  struct _QHASHLIST   *next;
+} QHASHLIST;
 
 /*
 **  A site may reject something in its subscription list if it has
@@ -451,6 +460,7 @@
   struct buffer	  Buffer;
   bool		  Buffered;
   char	      **  Originator;
+  QHASHLIST    *  QHashList;
   int		  Next;
   int		  Prev;
 } SITE;

Modified: innd/newsfeeds.c
===================================================================
--- innd/newsfeeds.c	2008-02-05 23:21:23 UTC (rev 7712)
+++ innd/newsfeeds.c	2008-03-20 14:26:12 UTC (rev 7713)
@@ -448,6 +448,7 @@
     int			isp;
     SITE		*nsp;
     struct buffer	b;
+    QHASHLIST           *qh;
 
     b = sp->Buffer;
     *sp = SITEnull;
@@ -467,6 +468,7 @@
     sp->NeedOverviewCreation = false;
     sp->FeedwithoutOriginator = false;
     sp->DropFiltered = false;
+    sp->QHashList = NULL;
 
     /* Nip off the first field, the site name. */
     if ((f2 = strchr(Entry, NF_FIELD_SEP)) == NULL)
@@ -598,6 +600,18 @@
             if (*++p && CTYPE(isdigit, *p))
                 sp->Nice = atoi(p);
             break;
+        case 'Q':
+            qh = xmalloc(sizeof(QHASHLIST));
+            p++;
+            if (sscanf(p, "%d/%d", &qh->begin, &qh->mod) == 2) {
+                qh->end = qh->begin;
+            } else if (sscanf(p, "%d-%d/%d", &qh->begin, &qh->end, &qh->mod) != 3) {
+                free(qh);
+                return "hash for Q not in x/z or x-y/z format";
+            }
+            qh->next = sp->QHashList;
+            sp->QHashList = qh;
+            break;
 	case 'S':
 	    if (*++p && CTYPE(isdigit, *p))
 		sp->StartSpooling = atol(p);

Modified: innd/site.c
===================================================================
--- innd/site.c	2008-02-05 23:21:23 UTC (rev 7712)
+++ innd/site.c	2008-03-20 14:26:12 UTC (rev 7713)
@@ -1005,6 +1005,7 @@
 SITEfree(SITE *sp)
 {
     SITE                *s;
+    QHASHLIST           *qh, *qn;
     int                 new;
     int                 i;
     
@@ -1059,6 +1060,10 @@
 	sp->FNLnames.data = NULL;
 	sp->FNLnames.size = 0;
     }
+    for (qh = sp->QHashList; qh; qh = qn) {
+        qn = qh->next;
+        free(qh);
+    }
 
     /* If this site was a master, find a new one. */
     if (sp->IsMaster) {



More information about the inn-committers mailing list