Virgin import of ntpd 4.2.6p5.

When the series of commits is complete, things like
https://cert.litnet.lt/en/docs/ntp-distributed-reflection-dos-attacks
should be fixed.

PR:		bin/148836 (except that we import a newer version)
Asked by:	Too many
MFC after:	2 weeks

1 files changed, 199 insertions, 0 deletions

diff --git a/ntpd/ntp_data_structures.c b/ntpd/ntp_data_structures.c
new file mode 100644
index 0000000..fb21529
--- /dev/null
+++ b/ntpd/ntp_data_structures.c
@@ -0,0 +1,199 @@
+/* ntp_data_structures.c
+ *
+ * This file contains the data structures used by the ntp configuration
+ * code and the discrete event simulator.
+ *
+ * Written By: Sachin Kamboj
+ *             University of Delaware
+ *             Newark, DE 19711
+ * Copyright (c) 2006
+ */
+
+
+#include <stdlib.h>    /* Needed for malloc */
+#include "ntp_data_structures.h"
+#include "ntp_stdlib.h"
+
+/* Priority Queue
+ * --------------
+ * Define a priority queue in which the relative priority of the elements
+ * is determined by a function 'get_order' which is supplied to the
+ * priority_queue
+ */
+
+
+queue *create_priority_queue(int (*get_order)(void *, void *))
+{
+    queue *my_queue = (queue *) emalloc(sizeof(queue));
+    my_queue->get_order = get_order;
+    my_queue->front = NULL;
+    my_queue->no_of_elements = 0;
+    return my_queue;
+}
+
+
+/* Define a function to "destroy" a priority queue, freeing-up
+ * all the allocated resources in the process 
+ */
+
+void destroy_queue(queue *my_queue)
+{
+    node *temp = NULL;
+
+    /* Empty out the queue elements if they are not already empty */
+    while (my_queue->front != NULL) {
+        temp = my_queue->front;
+        my_queue->front = my_queue->front->node_next;
+        free(temp);
+    }
+
+    /* Now free the queue */
+    free(my_queue);
+}
+
+
+/* Define a function to allocate memory for one element 
+ * of the queue. The allocated memory consists of size
+ * bytes plus the number of bytes needed for bookkeeping
+ */
+
+void *get_node(size_t size)
+{
+    node *new_node = emalloc(sizeof(*new_node) + size);
+    new_node->node_next = NULL; 
+    return new_node + 1;
+}
+
+/* Define a function to free the allocated memory for a queue node */
+void free_node(void *my_node)
+{
+    node *old_node = my_node;
+    free(old_node - 1);
+}
+
+
+void *
+next_node(
+	void *pv
+	)
+{
+	node *pn;
+
+	pn = pv;
+	pn--;
+
+	if (pn->node_next == NULL)
+		return NULL;
+
+	return pn->node_next + 1;
+}
+
+
+/* Define a function to check if the queue is empty. */
+int empty(queue *my_queue)
+{
+    return (!my_queue || !my_queue->front);
+}
+
+
+void *
+queue_head(
+	queue *q
+	)
+{
+	if (NULL == q || NULL == q->front)
+		return NULL;
+		
+	return q->front + 1;
+}
+
+
+/* Define a function to add an element to the priority queue.
+ * The element is added according to its priority - 
+ * relative priority is given by the get_order function
+ */
+queue *enqueue(queue *my_queue, void *my_node)
+{
+    node *new_node = ((node *) my_node) - 1;
+    node *i = NULL;
+    node *j = my_queue->front;
+
+    while (j != NULL && ((*my_queue->get_order)(new_node + 1, j + 1) > 0)) {
+        i = j;
+        j = j->node_next;
+    }
+    
+    if (i == NULL) {       /* Insert at beginning of the queue */
+        new_node->node_next = my_queue->front;
+        my_queue->front = new_node;
+    }
+    else {                /* Insert Elsewhere, including the end */
+        new_node->node_next = i->node_next;
+        i->node_next = new_node;
+    }
+
+    ++my_queue->no_of_elements;    
+    return my_queue;
+}
+
+
+/* Define a function to dequeue the first element from the priority
+ * queue and return it
+ */
+
+void *dequeue(queue *my_queue)
+{
+    node *my_node = my_queue->front;
+    if (my_node != NULL) {
+        my_queue->front = my_node->node_next;
+        --my_queue->no_of_elements;    
+        return (void *)(my_node + 1);
+    }
+    else
+        return NULL;
+}
+
+/* Define a function that returns the number of elements in the 
+ * priority queue
+ */
+int get_no_of_elements(queue *my_queue)
+{
+    return my_queue->no_of_elements;
+}
+
+/* Define a function to append a queue onto another.
+ * Note: there is a faster way (O(1) as opposed to O(n))
+ * to do this for simple (FIFO) queues, but we can't rely on
+ * that for priority queues. (Given the current representation)
+ * 
+ * I don't anticipate this to be a problem. If it does turn
+ * out to be a bottleneck, I will consider replacing the 
+ * current implementation with a binomial or fibonacci heap.
+ */
+
+void append_queue(queue *q1, queue *q2) 
+{
+    while (!empty(q2))
+        enqueue(q1, dequeue(q2));
+    destroy_queue(q2);
+}
+
+/* FIFO Queue
+ * ----------
+ * Use the priority queue to create a traditional FIFO queue.
+ * The only extra function needed is the create_queue 
+ */
+
+/* C is not Lisp and does not allow anonymous lambda functions :-(. 
+ * So define a get_fifo_order function here
+ */
+
+int get_fifo_order(void *el1, void *el2)
+{   return 1;
+}
+
+/* Define a function to create a FIFO queue */
+
+queue *create_queue()
+{    return create_priority_queue(get_fifo_order);
+}