/* Test allocation failures with dynamic arrays.

   Copyright (C) 2017-2018 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <http://www.gnu.org/licenses/>.  */

/* This test is separate from tst-dynarray because it cannot run under

   valgrind.  */

#include "tst-dynarray-shared.h"

#include <mcheck.h>

#include <stdio.h>

#include <support/check.h>

#include <support/support.h>

#include <support/xunistd.h>

#include <sys/mman.h>

#include <sys/resource.h>

#include <unistd.h>

/* Data structure to fill up the heap.  */

struct heap_filler

{

  struct heap_filler *next;

};

/* Allocate objects until the heap is full.  */

static struct heap_filler *

fill_heap (void)

{

  size_t pad = 4096;

  struct heap_filler *head = NULL;

  while (true)

    {

      struct heap_filler *new_head = malloc (sizeof (*new_head) + pad);

      if (new_head == NULL)

        {

          if (pad > 0)

            {

              /* Try again with smaller allocations.  */

              pad = 0;

              continue;

            }

          else

            break;

        }

      new_head->next = head;

      head = new_head;

    }

  return head;

}

/* Free the heap-filling allocations, so that we can continue testing

   and detect memory leaks elsewhere.  */

static void

free_fill_heap (struct heap_filler *head)

{

  while (head != NULL)

    {

      struct heap_filler *next = head->next;

      free (head);

      head = next;

    }

}

/* Check allocation failures for int arrays (without an element free

   function).  */

static void

test_int_fail (void)

{

  /* Exercise failure in add/emplace.

     do_add: Use emplace (false) or add (true) to add elements.

     do_finalize: Perform finalization at the end (instead of free).  */

  for (int do_add = 0; do_add < 2; ++do_add)

    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)

      {

        struct dynarray_int dyn;

        dynarray_int_init (&dyn);

        size_t count = 0;

        while (true)

          {

            if (do_add)

              {

                dynarray_int_add (&dyn, 0);

                if (dynarray_int_has_failed (&dyn))

                  break;

              }

            else

              {

                int *place = dynarray_int_emplace (&dyn);

                if (place == NULL)

                  break;

                TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));

                *place = 0;

              }

            ++count;

          }

        printf ("info: %s: failure after %zu elements\n", __func__, count);

        TEST_VERIFY_EXIT (dynarray_int_has_failed (&dyn));

        if (do_finalize)

          {

            struct int_array result = { (int *) (uintptr_t) -1, -1 };

            TEST_VERIFY_EXIT (!dynarray_int_finalize (&dyn, &result));

            TEST_VERIFY_EXIT (result.array == (int *) (uintptr_t) -1);

            TEST_VERIFY_EXIT (result.length == (size_t) -1);

          }

        else

          dynarray_int_free (&dyn);

        CHECK_INIT_STATE (int, &dyn);

      }

  /* Exercise failure in finalize.  */

  for (int do_add = 0; do_add < 2; ++do_add)

    {

      struct dynarray_int dyn;

      dynarray_int_init (&dyn);

      for (unsigned int i = 0; i < 10000; ++i)

        {

          if (do_add)

            {

              dynarray_int_add (&dyn, i);

              TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));

            }

          else

            {

              int *place = dynarray_int_emplace (&dyn);

              TEST_VERIFY_EXIT (place != NULL);

              *place = i;

            }

        }

      TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));

      struct heap_filler *heap_filler = fill_heap ();

      struct int_array result = { (int *) (uintptr_t) -1, -1 };

      TEST_VERIFY_EXIT (!dynarray_int_finalize (&dyn, &result));

      TEST_VERIFY_EXIT (result.array == (int *) (uintptr_t) -1);

      TEST_VERIFY_EXIT (result.length == (size_t) -1);

      CHECK_INIT_STATE (int, &dyn);

      free_fill_heap (heap_filler);

    }

  /* Exercise failure in resize.  */

  {

    struct dynarray_int dyn;

    dynarray_int_init (&dyn);

    struct heap_filler *heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_int_resize (&dyn, 1000));

    TEST_VERIFY (dynarray_int_has_failed (&dyn));

    free_fill_heap (heap_filler);

    dynarray_int_init (&dyn);

    TEST_VERIFY (dynarray_int_resize (&dyn, 1));

    heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_int_resize (&dyn, 1000));

    TEST_VERIFY (dynarray_int_has_failed (&dyn));

    free_fill_heap (heap_filler);

    dynarray_int_init (&dyn);

    TEST_VERIFY (dynarray_int_resize (&dyn, 1000));

    heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_int_resize (&dyn, 2000));

    TEST_VERIFY (dynarray_int_has_failed (&dyn));

    free_fill_heap (heap_filler);

  }

}

/* Check allocation failures for char * arrays (which automatically

   free the pointed-to strings).  */

static void

test_str_fail (void)

{

  /* Exercise failure in add/emplace.

     do_add: Use emplace (false) or add (true) to add elements.

     do_finalize: Perform finalization at the end (instead of free).  */

  for (int do_add = 0; do_add < 2; ++do_add)

    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)

      {

        struct dynarray_str dyn;

        dynarray_str_init (&dyn);

        size_t count = 0;

        while (true)

          {

            char **place;

            if (do_add)

              {

                dynarray_str_add (&dyn, NULL);

                if (dynarray_str_has_failed (&dyn))

                  break;

                else

                  place = dynarray_str_at (&dyn, dynarray_str_size (&dyn) - 1);

              }

            else

              {

                place = dynarray_str_emplace (&dyn);

                if (place == NULL)

                  break;

              }

            TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));

            TEST_VERIFY_EXIT (*place == NULL);

            *place = strdup ("placeholder");

            if (*place == NULL)

              {

                /* Second loop to wait for failure of

                   dynarray_str_emplace.  */

                while (true)

                  {

                    if (do_add)

                      {

                        dynarray_str_add (&dyn, NULL);

                        if (dynarray_str_has_failed (&dyn))

                          break;

                      }

                    else

                      {

                        char **place = dynarray_str_emplace (&dyn);

                        if (place == NULL)

                          break;

                        TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));

                        *place = NULL;

                      }

                    ++count;

                  }

                break;

              }

            ++count;

          }

        printf ("info: %s: failure after %zu elements\n", __func__, count);

        TEST_VERIFY_EXIT (dynarray_str_has_failed (&dyn));

        if (do_finalize)

          {

            struct str_array result = { (char **) (uintptr_t) -1, -1 };

            TEST_VERIFY_EXIT (!dynarray_str_finalize (&dyn, &result));

            TEST_VERIFY_EXIT (result.array == (char **) (uintptr_t) -1);

            TEST_VERIFY_EXIT (result.length == (size_t) -1);

          }

        else

          dynarray_str_free (&dyn);

        TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));

        TEST_VERIFY_EXIT (dyn.dynarray_header.array == dyn.scratch);

        TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == 0);

        TEST_VERIFY_EXIT (dyn.dynarray_header.allocated > 0);

      }

  /* Exercise failure in finalize.  */

  for (int do_add = 0; do_add < 2; ++do_add)

    {

      struct dynarray_str dyn;

      dynarray_str_init (&dyn);

      for (unsigned int i = 0; i < 1000; ++i)

        {

          if (do_add)

            dynarray_str_add (&dyn, xstrdup ("placeholder"));

          else

            {

              char **place = dynarray_str_emplace (&dyn);

              TEST_VERIFY_EXIT (place != NULL);

              TEST_VERIFY_EXIT (*place == NULL);

              *place = xstrdup ("placeholder");

            }

        }

      TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));

      struct heap_filler *heap_filler = fill_heap ();

      struct str_array result = { (char **) (uintptr_t) -1, -1 };

      TEST_VERIFY_EXIT (!dynarray_str_finalize (&dyn, &result));

      TEST_VERIFY_EXIT (result.array == (char **) (uintptr_t) -1);

      TEST_VERIFY_EXIT (result.length == (size_t) -1);

      TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));

      TEST_VERIFY_EXIT (dyn.dynarray_header.array == dyn.scratch);

      TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == 0);

      TEST_VERIFY_EXIT (dyn.dynarray_header.allocated > 0);

      free_fill_heap (heap_filler);

    }

  /* Exercise failure in resize.  */

  {

    struct dynarray_str dyn;

    dynarray_str_init (&dyn);

    struct heap_filler *heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_str_resize (&dyn, 1000));

    TEST_VERIFY (dynarray_str_has_failed (&dyn));

    free_fill_heap (heap_filler);

    dynarray_str_init (&dyn);

    TEST_VERIFY (dynarray_str_resize (&dyn, 1));

    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");

    heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_str_resize (&dyn, 1000));

    TEST_VERIFY (dynarray_str_has_failed (&dyn));

    free_fill_heap (heap_filler);

    dynarray_str_init (&dyn);

    TEST_VERIFY (dynarray_str_resize (&dyn, 1000));

    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");

    heap_filler = fill_heap ();

    TEST_VERIFY (!dynarray_str_resize (&dyn, 2000));

    TEST_VERIFY (dynarray_str_has_failed (&dyn));

    free_fill_heap (heap_filler);

  }

}

/* Test if mmap can allocate a page.  This is necessary because

   setrlimit does not fail even if it reduces the RLIMIT_AS limit

   below what is currently needed by the process.  */

static bool

mmap_works (void)

{

  void *ptr =  mmap (NULL, 1, PROT_READ | PROT_WRITE,

                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);

  if (ptr == MAP_FAILED)

    return false;

  xmunmap (ptr, 1);

  return true;

}

/* Set the RLIMIT_AS limit to the value in *LIMIT.  */

static void

xsetrlimit_as (const struct rlimit *limit)

{

  if (setrlimit (RLIMIT_AS, limit) != 0)

    FAIL_EXIT1 ("setrlimit (RLIMIT_AS, %lu): %m",

                (unsigned long) limit->rlim_cur);

}

/* Approximately this many bytes can be allocated after

   reduce_rlimit_as has run.  */

enum { as_limit_reserve = 2 * 1024 * 1024 };

/* Limit the size of the process, so that memory allocation in

   allocate_thread will eventually fail, without impacting the entire

   system.  By default, a dynamic limit which leaves room for 2 MiB is

   activated.  The TEST_RLIMIT_AS environment variable overrides

   it.  */

static void

reduce_rlimit_as (void)

{

  struct rlimit limit;

  if (getrlimit (RLIMIT_AS, &limit) != 0)

    FAIL_EXIT1 ("getrlimit (RLIMIT_AS) failed: %m");

  /* Use the TEST_RLIMIT_AS setting if available.  */

  {

    long target = 0;

    const char *variable = "TEST_RLIMIT_AS";

    const char *target_str = getenv (variable);

    if (target_str != NULL)

      {

        target = atoi (target_str);

        if (target <= 0)

          FAIL_EXIT1 ("invalid %s value: \"%s\"", variable, target_str);

        printf ("info: setting RLIMIT_AS to %ld MiB\n", target);

        target *= 1024 * 1024;      /* Convert to megabytes.  */

        limit.rlim_cur = target;

        xsetrlimit_as (&limit);

        return;

      }

  }

  /* Otherwise, try to find the limit with a binary search.  */

  unsigned long low = 1 << 20;

  limit.rlim_cur = low;

  xsetrlimit_as (&limit);

  /* Find working upper limit.  */

  unsigned long high = 1 << 30;

  while (true)

    {

      limit.rlim_cur = high;

      xsetrlimit_as (&limit);

      if (mmap_works ())

        break;

      if (2 * high < high)

        FAIL_EXIT1 ("cannot find upper AS limit");

      high *= 2;

    }

  /* Perform binary search.  */

  while ((high - low) > 128 * 1024)

    {

      unsigned long middle = (low + high) / 2;

      limit.rlim_cur = middle;

      xsetrlimit_as (&limit);

      if (mmap_works ())

        high = middle;

      else

        low = middle;

    }

  unsigned long target = high + as_limit_reserve;

  limit.rlim_cur = target;

  xsetrlimit_as (&limit);

  printf ("info: RLIMIT_AS limit: %lu bytes\n", target);

}

static int

do_test (void)

{

  mtrace ();

  reduce_rlimit_as ();

  test_int_fail ();

  test_str_fail ();

  return 0;

}

#define TIMEOUT 90

#include <support/test-driver.c>