Add the Inferno license to files we got from Inferno
[akaros.git] / kern / src / ns / random.c
index eaabae4..76cbfc4 100644 (file)
@@ -1,4 +1,31 @@
-// INFERNO
+/* Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
+ * Portions Copyright © 1997-1999 Vita Nuova Limited
+ * Portions Copyright © 2000-2007 Vita Nuova Holdings Limited
+ *                                (www.vitanuova.com)
+ * Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
+ *
+ * Modified for the Akaros operating system:
+ * Copyright (c) 2013-2014 The Regents of the University of California
+ * Copyright (c) 2013-2015 Google Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE. */
+
 #include <vfs.h>
 #include <kfs.h>
 #include <slab.h>
 #include <cpio.h>
 #include <pmap.h>
 #include <smp.h>
-#include <ip.h>
-
-static struct
-{
-       qlock_t qlock;
-       struct rendez   producer;
-       struct rendez consumer;
-       uint32_t        randomcount;
-       uint8_t buf[1024];
-       uint8_t *ep;
-       uint8_t *rp;
-       uint8_t *wp;
-       uint8_t next;
-       uint8_t bits;
-       uint8_t wakeme;
-       uint8_t filled;
-       int     target;
-       int     kprocstarted;
-       uint32_t        randn;
-} rb;
+#include <apipe.h>
 
-static int
-rbnotfull(void*unused)
-{
-       int i;
-
-       i = rb.wp - rb.rp;
-       if(i < 0)
-               i += sizeof(rb.buf);
-       return i < rb.target;
-}
+#define RAND_BUF_SZ 1024
 
-static int
-rbnotempty(void*unused)
-{
-       return rb.wp != rb.rp;
-}
+static struct rb {
+       uint8_t buf[RAND_BUF_SZ];
+       struct atomic_pipe ap;
+} rb;
 
-static void
-genrandom(void*unused)
+/* The old style seemed to have genrandom incrementing a shared mem variable,
+ * randomcount, while randomclock, sort of an interrupt handler, would use this
+ * variable to generate random numbers.  They needed to run concurrently to get
+ * some sort of randonmess.  To do so, randomclock wouldn't run if genrandom
+ * wasn't in the process of incrementing the variable.  So we'd need genrandom
+ * working (in the background, but that doesn't work so well for us), when the
+ * randomclock alarm fired.  Then we could get 2 bits.  We'd do that 4 times
+ * to make our random byte.
+ *
+ * In akaros, genrandom would spin to 100,000 every time, without interruption,
+ * since the randomcount's alarm wouldn't interrupt: they are both routine
+ * kernel messages.  So we might as well just call kthread yield each time.
+ * Even then, it was still really slow.  This was because we only got 2 bits of
+ * randomness every 13ms (randomcount would make 2 bits per run, it would run
+ * once every 13ms, unless I screwed up the math on that.  It was supposed to
+ * run with a "Frequency close but not equal to HZ").
+ *
+ * We'd also use the old random values in the ring buffer to muck with the
+ * randomness. */
+static void genrandom(void *unused)
 {
-#warning "priority?"
+       uint8_t rand_two_bits, rp_byte, wp_byte;
+       uint8_t rand_byte = 0;
+       unsigned int mod_four = 0;
        //setpri(PriBackground);
 
-       for(;;) {
-               for(;;)
-                       if(++rb.randomcount > 100000)
-                               break;
-               //if(anyhigher())
-               //      sched();
-               if(rb.filled || !rbnotfull(0))
-                       rendez_sleep(&rb.producer, rbnotfull, 0);
-       }
-}
+       for (;;) {
+               /* this seems just as good (or bad) as the old genrandom incrementing a
+                * shared memory variable concurrently */
+               rand_two_bits = read_tsc() & 0x3;
+               rand_byte = (rand_byte << 2) ^ rand_two_bits;
 
-/*
- *  produce random bits in a circular buffer
- */
-static void
-randomclock(void)
-{
-       uint8_t *p;
+               /* put in a kthread_yield or something here, if we want to replicate the
+                * way randomclock would return, waiting til its next tick to get two
+                * more bits. */
 
-       if(rb.randomcount == 0)
-               return;
+               /* every four times, we built a full random byte */
+               if (++mod_four % 4 == 0)
+                       continue;
 
-       if(!rbnotfull(0)) {
-               rb.filled = 1;
-               return;
+               /* the old plan9 generator would xor our rand_byte with both the value
+                * of the read pointer and the write pointer:
+                *      *rb.wp ^= rb.bits ^ *rb.rp;
+                * we'll peak into the apipe to do the same */
+               rp_byte = rb.buf[rb.ap.ap_rd_off & (RAND_BUF_SZ - 1)];
+               wp_byte = rb.buf[rb.ap.ap_wr_off & (RAND_BUF_SZ - 1)];
+               rand_byte ^= rp_byte ^ wp_byte;
+               apipe_write(&rb.ap, &rand_byte, 1);
        }
-
-       rb.bits = (rb.bits<<2) ^ (rb.randomcount&3);
-       rb.randomcount = 0;
-
-       rb.next += 2;
-       if(rb.next != 8)
-               return;
-
-       rb.next = 0;
-       *rb.wp ^= rb.bits ^ *rb.rp;
-       p = rb.wp+1;
-       if(p == rb.ep)
-               p = rb.buf;
-       rb.wp = p;
-
-       if(rb.wakeme)
-               rendez_wakeup(&rb.consumer);
 }
 
-void
-randominit(void)
+void randominit(void)
 {
-       qlock_init(&rb.qlock);
-       rendez_init(&rb.producer);
-       rendez_init(&rb.consumer);
-       /* Frequency close but not equal to HZ */
-       //addclock0link(randomclock, 13);
-       rb.target = 16;
-       rb.ep = rb.buf + sizeof(rb.buf);
-       rb.rp = rb.wp = rb.buf;
+       apipe_init(&rb.ap, rb.buf, sizeof(rb.buf), 1);
+       ktask("genrandom", genrandom, 0);
 }
 
-/*
- *  consume random bytes from a circular buffer
- */
-uint32_t
-randomread(void *xp, uint32_t n)
+uint32_t randomread(void *buf, uint32_t n)
 {
-       ERRSTACK(1);
-       int i, sofar;
-       uint8_t *e, *p;
-
-       p = xp;
-
-       qlock(&(&rb)->qlock);
-       if(waserror()){
-               qunlock(&(&rb)->qlock);
-               nexterror();
-       }
-       if(!rb.kprocstarted){
-               rb.kprocstarted = 1;
-               ktask("genrand", genrandom, NULL);
+       int amt;
+       uint32_t ret = 0;
+
+       for (int i = 0; i < n; i++) {
+               /* read the random byte directly into the (user) buffer */
+               amt = apipe_read(&rb.ap, buf, 1);
+               if (amt < 0)
+                       error(EFAIL, "randomread apipe");
+               if (amt != 1)
+                       warn("Odd amount read from random apipe");
+               buf++;
+               ret += amt;
        }
-
-       for(sofar = 0; sofar < n; sofar += i){
-               i = rb.wp - rb.rp;
-               if(i == 0){
-                       rb.wakeme = 1;
-                       rendez_wakeup(&rb.producer);
-                       rendez_sleep(&rb.consumer, rbnotempty, 0);
-                       rb.wakeme = 0;
-                       continue;
-               }
-               if(i < 0)
-                       i = rb.ep - rb.rp;
-               if((i+sofar) > n)
-                       i = n - sofar;
-               memmove(p + sofar, rb.rp, i);
-               e = rb.rp + i;
-               if(e == rb.ep)
-                       e = rb.buf;
-               rb.rp = e;
-       }
-       if(rb.filled && rb.wp == rb.rp){
-               i = 2*rb.target;
-               if(i > sizeof(rb.buf) - 1)
-                       i = sizeof(rb.buf) - 1;
-               rb.target = i;
-               rb.filled = 0;
-       }
-       poperror();
-       qunlock(&(&rb)->qlock);
-
-       rendez_wakeup(&rb.producer);
-
-       return n;
+       return ret;
 }