Как исправить утечки памяти Valgrind?

#c #debugging

#c #отладка

Вопрос:

Я пытаюсь реализовать базовый список пропусков, но я не могу понять, в чем проблема, потому что, когда я запускаю его, он выдает ошибку Segmentaion.

Я использовал Valgrind для проверки утечек памяти, и это выдает мне некоторые ОПРЕДЕЛЕННО потерянные блоки ошибок.

Я запускаю Valgrind следующим образом :

valgrind --leak-check=full --show-leak-kinds=all -v ./myProgram

Я попытался удалить то, что можно удалить, но это дает мне тот же результат плюс некоторые другие ошибки.

 ==20782== HEAP SUMMARY:
==20782==     in use at exit: 96 bytes in 2 blocks
==20782==   total heap usage: 14 allocs, 12 frees, 81,976 bytes allocated
==20782== 
==20782== Searching for pointers to 2 not-freed blocks
==20782== Checked 111,288 bytes
==20782== 
==20782== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==20782==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==20782==    by 0x1096AA: SkipList<int>::insertID(int, int) (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782==    by 0x109395: main (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782== 
==20782== 48 bytes in 1 blocks are definitely lost in loss record 2 of 2
==20782==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==20782==    by 0x1096CD: SkipList<int>::insertID(int, int) (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782==    by 0x109395: main (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782== 
==20782== LEAK SUMMARY:
==20782==    definitely lost: 96 bytes in 2 blocks
==20782==    indirectly lost: 0 bytes in 0 blocks
==20782==      possibly lost: 0 bytes in 0 blocks
==20782==    still reachable: 0 bytes in 0 blocks
==20782==         suppressed: 0 bytes in 0 blocks
==20782== 
==20782== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
==20782== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

  

SkipList.h

 using namespace std;

#define MIN_ID 0
#define MAX_ID 999999
#define NULL_SCORE 0

template < class T >
class Node {
public:
   T level;
   T ID;
   T score;
   Node<T>* next;
   Node<T>* prev;
   Node<T>* below;
   Node<T>* above;

   Node() {
      next = NULL;
      prev = NULL;
      below = NULL;
      above = NULL;
   }

   Node(T ID, T score) {
      this->level = 1;
      this->ID = ID;
      this->score = score;
      next = NULL;
      prev = NULL;
      below = NULL;
      above = NULL; 
   }

   Node(const Nodeamp; node) : level(node->level), ID(node->ID), score(node->score) {

   }

   Nodeamp; operator=(const Nodeamp; node) {
      level = node->level;
      ID = node->ID;
      score = node->score;
      return *this;
   }

   ~Node() {}

   T getScore() {
      return this->score;
   }

   T getID() {
      return this->ID;
   }

   T getLeve() {
      return this->level;
   }

   T setScore(T score) {
      T old_score;
      old_score = this->score;
      this->score = score;
      return old_score;
   }
};

template < class T >
class SkipList {
public:
   Node<T>* head;
   Node<T>* tail;
   Node<T>* p1;
   Node<T>* p2;
   T height;
   T no_entries;

   SkipList() {
      p1 = new Node<T>(MIN_ID, NULL_SCORE);
      p2 = new Node<T>(MAX_ID, NULL_SCORE);
      head = p1;
      tail = p2;
      p1->next = p2;
      p2->prev = p1;
      height = 1;
      no_entries = 0;
   }

   ~SkipList() {
      delete p1;
      delete p2;
   }

   SkipList(const SkipListamp; SkipList) : height(SkipList->height), no_entries(SkipList->no_entries) {

   }

   SkipListamp; operator=(const SkipListamp; SkipList) {
      height = SkipList->height;
      no_entries = SkipList->no_entries;
      return *this;
   }

   T getSize() {
      return this->no_entries;
   }

   T getHeight() {
      return this->height;
   }

   bool isEmpty() {
      if (no_entries == 0) {
         return true;
      }else {
         return false;
      }
   }

   T getScore(T ID) {
      Node<T>* p;
      p = searchID(ID);
      if (p.getID() == ID ) {
         return p->score;
      }else {
         return NULL;
      }
   }

   string coinFlip() {
      string s;
      string str1 = "Heads";
      string str2 = "Tails";
      int r;
      srand(time(0));
      for (int i = 1; i < 2; i  ) {
        r = 1   (rand() %2);
      }
      if (r == 1) {
         s.assign(str1);
      }else if (r == 2) {
         s.assign(str2);
      }
      return s;
   }

   Node<T>* insertAbove(Node<T>* p, Node<T>* e, T ID, T score) {
      e = new Node<T>(ID, score);

      p->above = e;
      e->below = p;

      e->below->prev->above->next = e;
      e->prev = e->below->prev->above;

      e->below->next->above->prev = e;
      e->next = e->below->next->above;

      delete e;
      return e;

   }

   Node<T>* searchID(T ID) {
      Node<T>* p;
      p = head;
      while (p->below != NULL) {
         p = p->below;
         while (ID >= p->next->ID) {
            p = p->next;
         }
      }
      return p;
   }

   Node<T>* insertID(T ID, T score) {
      Node<T>* aux1;
      Node<T>* new_node1 = new Node<T>(ID, score);

      aux1 = searchID(ID);

      aux1->next = new_node1;
      new_node1->prev = aux1;
      new_node1->next = tail;

      while (coinFlip() == "Heads"); {
         if (new_node1->level >= height) {
            height  ;
            Node<T>* new_node2 = new Node<T>(ID, score);

            //Create a new empty layer
            Node<T>* p1 = new Node<T>(MIN_ID, NULL_SCORE);
            Node<T>* p2 = new Node<T>(MAX_ID, NULL_SCORE);

            //Making the connections
            head->above = p1;
            tail->above = p2;

            p1->below = head;
            p2->below = tail;

            p1 = head;
            p2 = tail;

            while (aux1->above == NULL) {
               aux1 = aux1->prev;
            }
            aux1 = aux1->above;

            insertAbove(new_node1, new_node2, ID, score);

            new_node1->level  ;
            delete new_node2;
         }
      }
      no_entries  ;
      delete new_node1;
      return new_node1;
   }

   bool deleteID(T ID) {
      Node<T>* current = head;
      bool found = false;
      if (current->next == NULL amp;amp; current->next->ID == ID) {
         found = true;
         current->next = current->next->next;
         no_entries--;
      }
      delete current;
      return found;
   }
};
  

main.cpp

 #include <fstream>
#include <iostream>
#include <sstream>
#include <string>

#include "SkipList.h"

using namespace std;
int main() {
   SkipList<int>* my_SkipList = new SkipList<int>();

   for (int i = 0; i < 5; i  ) {
      my_SkipList->insertID(i, i);
   }

   return 0;
}
  

Комментарии:

1. Используйте интеллектуальные указатели.

2. @Quentin Я не могу этого сделать, поскольку это часть моей домашней работы, и мне не разрешено использовать функции из STL, и я могу использовать только несколько библиотек для C / C

3. «ВСЕ ЕЩЕ ДОСТУПНЫЕ БЛОКИ не настолько вредны» — Это может быть правдой, но это показывает, что в вашем коде происходит что-то, чего вы не понимаете. Это что-то, при других обстоятельствах, может быть вредным.

4. @BennyK Итак, что я могу сделать, чтобы решить мою проблему? Например, я дважды использую ключевое слово new в своем конструкторе и удаляю эти объекты в Destructor, пока не получу тот же результат, но если я удаляю те же объекты в Constructor, ошибки / предупреждения от Valgrind увеличиваются с 9 до 4. Итак, что мне нужно понять из этого?

5. Исправьте ошибку сегментации, прежде чем беспокоиться о любых утечках памяти. Если код, который должен был бы корректно устранить сбои, скорее всего, у него просто не было возможности что-то удалить. Не обязательно проблема, но оба ваших класса нарушают правило трех / пяти. Хотя на первый взгляд я не вижу, чтобы что-то их копировало, поэтому вы могли бы просто определить конструкторы копирования и присваивание как удаленные, а не внедрять их.

Ответ №1:

(Я предполагаю, что вы добавили delete my_SkipList в конце main .)

Если вы компилируете с отладочной информацией, лучше всего без оптимизации (параметры часто зависят от компилятора -g -O0 ), valgrind показывает номера строк обнаруженных проблем, например

 ==23956== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==23956==    at 0x4C266E7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23956==    by 0x400E94: SkipList<int>::insertID(int, int) (SkipList.h:194)
==23956==    by 0x400C40: main (main.cpp:13)
==23956== 
==23956== 48 bytes in 1 blocks are definitely lost in loss record 2 of 2
==23956==    at 0x4C266E7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23956==    by 0x400EB7: SkipList<int>::insertID(int, int) (SkipList.h:195)
==23956==    by 0x400C40: main (main.cpp:13)
  

Из этого мы можем легко видеть, что непревзойденные распределения являются

             //Create a new empty layer
            Node<T>* p1 = new Node<T>(MIN_ID, NULL_SCORE);
            Node<T>* p2 = new Node<T>(MAX_ID, NULL_SCORE);
  

Отсюда мы можем определить, с чем связаны ошибки.

  1. Вы не должны delete удалять узлы, которые являются частью существующих SkipList , т.е. delete e from insertAbove() и delete new_node1 from insertID() .

  2. В insertID() коде для вставки new_node1

           aux1->next = new_node1;
          new_node1->prev = aux1;
          new_node1->next = tail;
      

    неверно предполагать, что следующий узел всегда был tail ; лучше:

           new_node1->next = aux1->next; // next isn't necessarily tail
          aux1->next = new_node1;
          new_node1->prev = aux1;
      
  3. Прежде всего, деструктора, ~SkipList() освобождающего только два узла, выделенных в конструкторе, недостаточно — скорее, также должны быть освобождены все узлы, выделенные позже для SkipList , например.:

        ~SkipList()
       {
            for (Node<T> *p, *c; p = head; )
            {
                head = head->above;
                do c = p, p = p->next, delete c; while (p);
            }
       }
      

Обратите внимание, что эти пункты устраняют только ошибки выделения в коде, а не любую другую логическую ошибку.