thodg/libgit2/tests/core/pqueue.c

• Show log

  Commit

• Hash : 95fa3880
  Author :
  Date : 2016-10-28T16:07:40
  

  pqueue: resolve possible NULL pointer dereference
  
  The `git_pqueue` struct allows being fixed in its total number of
  entries. In this case, we simply throw away items that are
  inserted into the priority queue by examining wether the new item
  to be inserted has a higher priority than the previous smallest
  one.
  
  This feature somewhat contradicts our pqueue implementation in
  that it is allowed to not have a comparison function. In fact, we
  also fail to check if the comparison function is actually set in
  the case where we add a new item into a fully filled fixed-size
  pqueue.
  
  As we cannot determine which item is the smallest item in absence
  of a comparison function, we fix the `NULL` pointer dereference
  by simply dropping all new items which are about to be inserted
  into a full fixed-size pqueue.
  

Download

• tests/core/pqueue.c

• #include "clar_libgit2.h"
  #include "pqueue.h"
  
  static int cmp_ints(const void *v1, const void *v2)
  {
  	int i1 = *(int *)v1, i2 = *(int *)v2;
  	return (i1 < i2) ? -1 : (i1 > i2) ? 1 : 0;
  }
  
  void test_core_pqueue__items_are_put_in_order(void)
  {
  	git_pqueue pq;
  	int i, vals[20];
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
  
  	for (i = 0; i < 20; ++i) {
  		if (i < 10)
  			vals[i] = 10 - i; /* 10 down to 1 */
  		else
  			vals[i] = i + 1;  /* 11 up to 20 */
  
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  	}
  
  	cl_assert_equal_i(20, git_pqueue_size(&pq));
  
  	for (i = 1; i <= 20; ++i) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(i, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__interleave_inserts_and_pops(void)
  {
  	git_pqueue pq;
  	int chunk, v, i, vals[200];
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
  
  	for (v = 0, chunk = 20; chunk <= 200; chunk += 20) {
  		/* push the next 20 */
  		for (; v < chunk; ++v) {
  			vals[v] = (v & 1) ? 200 - v : v;
  			cl_git_pass(git_pqueue_insert(&pq, &vals[v]));
  		}
  
  		/* pop the lowest 10 */
  		for (i = 0; i < 10; ++i)
  			(void)git_pqueue_pop(&pq);
  	}
  
  	cl_assert_equal_i(100, git_pqueue_size(&pq));
  
  	/* at this point, we've popped 0-99 */
  
  	for (v = 100; v < 200; ++v) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(v, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__max_heap_size(void)
  {
  	git_pqueue pq;
  	int i, vals[100];
  
  	cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, cmp_ints));
  
  	for (i = 0; i < 100; ++i) {
  		vals[i] = (i & 1) ? 100 - i : i;
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  	}
  
  	cl_assert_equal_i(50, git_pqueue_size(&pq));
  
  	for (i = 50; i < 100; ++i) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(i, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__max_heap_size_without_comparison(void)
  {
  	git_pqueue pq;
  	int i, vals[100] = { 0 };
  
  	cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, NULL));
  
  	for (i = 0; i < 100; ++i)
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  
  	cl_assert_equal_i(50, git_pqueue_size(&pq));
  
  	/* As we have no comparison function, we cannot make any
  	 * actual assumptions about which entries are part of the
  	 * pqueue */
  	for (i = 0; i < 50; ++i)
  		cl_assert(git_pqueue_pop(&pq));
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  static int cmp_ints_like_commit_time(const void *a, const void *b)
  {
  	return *((const int *)a) < *((const int *)b);
  }
  
  void test_core_pqueue__interleaved_pushes_and_pops(void)
  {
  	git_pqueue pq;
  	int i, j, *val;
  	static int commands[] =
  		{ 6, 9, 8, 0, 5, 0, 7, 0, 4, 3, 0, 0, 0, 4, 0, 2, 0, 1, 0, 0, -1 };
  	static int expected[] =
  		{ 9, 8, 7, 6, 5, 4, 4, 3, 2, 1, -1 };
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 10, cmp_ints_like_commit_time));
  
  	for (i = 0, j = 0; commands[i] >= 0; ++i) {
  		if (!commands[i]) {
  			cl_assert((val = git_pqueue_pop(&pq)) != NULL);
  			cl_assert_equal_i(expected[j], *val);
  			++j;
  		} else {
  			cl_git_pass(git_pqueue_insert(&pq, &commands[i]));
  		}
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  	git_pqueue_free(&pq);
  }
  
  

Download