IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

free() invalid size très bizarre


Sujet :

C++

  1. #1
    Membre confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Par défaut free() invalid size très bizarre
    Bonjour,

    Merci par avance à tous ceux qui essaieront de m'aider, je vous poste le code et je vous dis ce qui se passe !

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    #ifndef JOHNSON_P
    #define JOHNSON_P
     
    #include "preprocesscl.hpp"
    #include "bellmanfordcl.hpp"
    #include "dijkstracl.hpp"
     
    #include <vector>
    #include <iostream>
     
    /*
        This module provides an implementation of the Johnson's algorithm for computing
        all shortest-paths in a graph that does not contain any negative-weight cycle
    */
     
    template<typename Tvertex, typename Tweight>
    std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph);
    /*
        Aim : compute new weights for the graph in order to later apply Dijkstra's algorithm
        Args : the graph
        Return value : none
        Complexity : O(nm)    (reduces to one invocation of Bellman-Ford algorithm)
    */
     
    template<typename Tvertex, typename Tweight>
    std::vector<std::vector<Tweight>> johnson(graph<Tvertex, Tweight>& my_graph);
    /*
        Aim : compute all shortest-paths between all pairs of vertices of the graph
        Args : a graph
        Return value : a 2D vector that contains all shortest-paths
        Complexity : O(nmlog(n))
    */
     
    // OpenCL version, kind of have to specify the parameters for the template
    //void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances);
     
    template<typename Tvertex, typename Tweight>
    std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph){
     
        std::vector<std::vector<Tweight>> copy_graph = my_graph;           // so that we do not consider all fictitious edges after this function
     
        // we add a fictitious vertex   
     
        std::vector<Tweight> fictitious_edges(std::vector<Tweight>(my_graph.size()));
        copy_graph.push_back(fictitious_edges);
        for(size_t i = 0; i < my_graph.size(); i++)
            copy_graph[i][my_graph.size()] = std::numeric_limits<double>::max() /2 ;
     
        std::vector<Tweight> new_weights = bellman_ford(copy_graph, copy_graph.size()-1); // apply bellman-ford on the graph using the fictitious vertex
                                                                                            // as the source
        for(size_t i = 0; i < my_graph.size(); i++){
            for(size_t j = 0; j < my_graph.size(); j++){
                my_graph[i][j] += new_weights[i] - new_weights[j]; // update the edges
            }
        }
     
        return new_weights;
    }
     
    template<typename Tvertex, typename Tweight>
    std::vector<std::vector<Tweight>> johnson(std::vector<std::vector<Tweight>>& my_graph){
     
        std::vector<std::vector<Tweight>> distances(my_graph.size(), std::vector<Tweight>(my_graph.size(), std::numeric_limits<Tweight>::max()));
     
        std::vector<Tweight> weights = reweight<Tvertex, Tweight>(my_graph);
     
        for(size_t i = 0; i < my_graph.size(); i++){
            std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i);
            for(size_t j = 0; j < my_graph.size(); ++j){
                std::cout << "i : " << i << " j  " << j << std::endl;
                //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max())
                //    distances[i][j] = shortest_paths_from_i[j];
                //else
                //    distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i];
            }
        }
     
        return distances;
    }
    /*
    void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances){
     
        cl::Kernel kernel(prog, "johnson");
        kernel.setArg(0, (cl_uint) n_nodes);
        kernel.setArg(1, my_graph);
        kernel.setArg(2, distances);
        size_t group_size = 16;
        cl::NDRange local(group_size, group_size);
        cl::NDRange global((n_nodes + group_size - 1) / group_size * group_size,
                           (n_nodes + group_size - 1) / group_size * group_size);
        cmdQueue.enqueueNDRangeKernel(kernel, cl::NullRange, global, local);
     
    }
     */
    #endif
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include "preprocesscl.hpp"
    #include "bellmanfordcl.hpp"
    #include "johnsoncl.hpp"
    #include "dijkstracl.hpp"
    #include <chrono>
    //#include <omp.h>
     
     
    //#include "boost/graph/johnson_all_pairs_shortest.hpp"
     
    #include <iostream>
     
    int main(int argc, char* argv[]){
    /*
        std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]);
     
        std::vector<double> distances = bellman_ford<long unsigned int, double>(my_graph, 0);
     
        std::vector<double> new_w = reweight<long unsigned int, double>(my_graph);
     
        for(size_t k = 0 ; k < new_w.size(); k++)
            std::cout << new_w[k] << " " ;
        std::cout << std::endl << std::endl;
     
        std::vector<double> distances_d = dijkstra(my_graph, 0);
     
        for(size_t i = 0; i < distances_d.size(); i++){
            std::cout << distances_d[i] << " " ;
        }
     
        std::cout << std::endl;
    */
     
        std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]);
     
        std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
     
        std::vector<std::vector<double>> distances = johnson<long unsigned int, double>(my_graph);
     
        std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
     
        std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
     
        std::cout << time_span.count();
        std::cout << std::endl;
     
     
        return 0;
     
    }
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    #ifndef DIJKSTRA_P
    #define DIJKSTRA_P
     
    #include <iostream>
    #include <vector>
    #include "heap_generic.hpp"
    #include "preprocesscl.hpp"
    #include <limits>
    #include <omp.h>
     
    /*
     
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
     
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
            std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
     
            std::cout << time_span.count();
            std::cout << std::endl;
    */
    template<typename Tnode, typename Tweight>
    struct dijkstra_pair {
        Tnode pivot;
        Tweight key;
     
        bool operator<(dijkstra_pair &other_pair){
            return key < other_pair.key;
        }
     
        bool operator>(dijkstra_pair &other_pair){
            return key > other_pair.key; 
        }
    };
     
    template<typename Tnode, typename Tweight>
    std::ostream& operator<<(std::ostream& out, const dijkstra_pair<Tnode, Tweight>& pair){
        out << "Vertex : " << pair.pivot << ", key : " << pair.key << std::endl;
        return out;
    }
     
    template<typename Tnode, typename Tweight>
    std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode node);
    /*
        Aim : compute the shortest distances from source to every other vertex
        Args : the graph, represented as defined in preprocess.hpp and a source vertex
        Return value : a 1D array that contains the shortest distances
        Complexity : O(mlog(n))
    */
     
    template<typename Tnode, typename Tweight>
    std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source);
    /*
        Aim : initialize the shortest paths, a shortest path is equal to the value of the edge between source and vertex if it exists, 0 between source
              and source, infinity represented as numeric_limits<Tweight>::max() otherwise
        Args : a graph and a source node
        Return value : a 1D array containing all initialized distances
        Complexity : O(n)
    */
     
    template<typename Tnode, typename Tweight>
    std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){
     
        //to store our computed distances
        std::vector<Tweight> distances = initialize_distances(my_graph, source);
     
     
        std::vector<bool> in_heap(my_graph.size(), false);                  // to keep track of nodes in the heap
        std::vector<bool> processed(my_graph.size(), false);                // to keep track of processed nodes
     
        std::vector<dijkstra_pair<Tnode, Tweight>> heap = create_heap<dijkstra_pair<Tnode, Tweight>>();        // our amazing heap for BLAZINGLY FAST
                                                                                                               // implementation
     
        insert(heap, {source, 0});             // insert the source and mark it as "in the heap"
        in_heap[source] = true;
     
        while(size_heap(heap) != 1){
     
            dijkstra_pair<Tnode, Tweight> new_pair = pop(heap);
            in_heap[new_pair.pivot] = false;                             // old min is not in the heap anymore
            processed[new_pair.pivot] = true;                            // old min is now processed           
            distances[new_pair.pivot] = new_pair.key;                    // the old key is the permanent distance between source and associated node
     
            for(size_t i = 0; i < my_graph.size(); i++){          // we check all outgoing edges of the new added vertex
     
                edge<Tnode, Tweight> current_edge{new_pair.pivot, i, my_graph[new_pair.pivot][i]};
                Tnode current_node = current_edge.head_;                                 // the head of an outgoing edge whose tail is the new added vertex
     
                 // if already in the heap we update its key
                if(in_heap[current_node]){                                              
     
                    Tweight old_key = delete_element(heap, current_node).key;
                    Tweight new_key = std::min(old_key, distances[new_pair.pivot] + current_edge.weight_);
                    insert(heap, {current_node, new_key});
                }
     
                else if(!processed[current_node]){   
     
                    // otherwise we compute its key and insert it
                    //Tweight new_key = compute_key(my_graph, current_node, in_heap, distances);
                    Tweight new_key = distances[new_pair.pivot] + current_edge.weight_;
                    insert(heap, {current_node, new_key});
     
                    in_heap[current_node] = true;
                }
            }
        }
     
        return distances;
    }
     
    template<typename Tnode, typename Tweight>
    std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){
        std::vector<Tweight> distances(my_graph.size(), std::numeric_limits<Tweight>::max()/2);                  // std::numeric_limits<int> causes dist[smth] 
                                                                                        // + stuff to be -X which is always less than current key
        distances[source] = 0;
        for(size_t i = 0; i < my_graph.size(); i++)
            distances[my_graph[source][i]] = my_graph[source][i];
     
        return distances;
    }
     
    #endif
    Le premier fichier contient deux fonctions une fonction qui permet de calculer des valeurs pour la deuxième qui perform l'algorithme de johnson.

    Le main qui ne fait qu'appeler johnson et qui record le temps que ça prend .

    Le troisième qui contient la fonction qui perform l'algorithme de dijkstra.

    Voici l'erreur qui me rend fou : free(): invalid next size (fast): 0x0000000001d3e840 ***

    Le plus dingue : l'erreur intervient dans la boucle :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(size_t i = 0; i < my_graph.size(); i++){
            std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i);
            for(size_t j = 0; j < my_graph.size(); ++j){
                std::cout << "i : " << i << " j  " << j << std::endl;
                //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max())
                //    distances[i][j] = shortest_paths_from_i[j];
                //else
                //    distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i];
            }
        }
    Lorsque i = 3. Cependant (oui vous allez voir c'est marrant), si à la place de i je mets 0 tout va bien (j'applique my_graph.size() l'algo de dijkstra avec le node 0 comme node source, vu que c'est pas celui là qui plantait ça me emble logique). Si à la place je mets 1 ça fonctionne, si à la place je mets 2 ça fonctionne une fois puis au second appel de dijkstra ça plante (alors que à la base c'est pas l'itération pour i = 2 qui plante), si je mets 3 ça fonctionne (c'est l'itération qui plantait...). Si je mets 4 5 6 ou 7 ça marche (mon petit exemple ne contient que 8 nodes).

    Quelq'un a t-il une idée de ce qu'il se passe ? J'ai lu sur le forum et ailleurs que cette erreur survient lors de dépassements de mémoire, de double free, de tentative d'accès à de la mémoire non allouée...

    Cependant ici l'itération qui plante de base c'est lorsque j'appelle dijkstra<Tvertex, Tweight>(my_graph, 3), qui ne plante pas dans si j'écris dans ma boucle dijkstra<Tvertex, Tweight>(my_graph, 1 ou 2 ou 3 jusqu'à 7)

    Donc je me dis, peut-être que mes itérations 0 ou 1 ou 2 provoquent des choses qui font que pour i = 3 ça plante (raison pour laquelle si je commence par la 3 ça ne plante pas par exemple). Cependant ma fonction dijkstra ne touchent pas à ses arguments déclarés "const" elle ne fait que retourner un std::vector<Tweight> (vous pouvez penser Tweight = double si vous voulez), du coup j'ai pas la moindre idée de ce qu'il se passe...

    Merci encore à tous

  2. #2
    Expert confirmé
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 292
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Août 2003
    Messages : 5 292
    Par défaut
    Je vois des tailles employées qui ne correspondent pas à celles de l'objet manipulé. Pour moi que la matrice soit carrée mérite un assert pour le clarifier.

    Sinon, ton problème est un boulot pour valgrind, ou mieux le mode sanatize=address de clang (les derniers gcc l'ont aussi maintenant). Passer ta SL en mode checké peut être pas mal aussi.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  3. #3
    Membre confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Par défaut
    Bonsoir et merci Monsieur Hermitte, des tailles employées qui ne correspondent pas à l'objet manipulé ? Puis-je savoir où ? car c'est le premier truc que j'ai cherché à vérifier, j'ai tout print avant la dernière boucle que j'ai montré (celle dans laquelle on appelle dijkstra) et jusque là le graphe contient exactement ce qu'il doit contenir, il fait une taille de 8 par 8. Est-ce que vous avez un tuto simple pour valgrind ? Je suis assez pressé avec ce projet je voudrais bien trouver l'erreur rapidement.

    Merci encore

  4. #4
    Expert confirmé
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 292
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Août 2003
    Messages : 5 292
    Par défaut
    Typiquement, entre la ligne 46 et 47 du premier fichier, cela mérite un
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    assert(copy_graph[i].size() > my_graph.size());
    Je n'ai pas tout regardé, mais s'il doit y avoir d'autres "évidences" du genre, les énoncer clairement n'est jamais une perte de temps -- un collègue avait des problèmes similaires il y a une 10aines de jours, et ... il a pu constater l'efficacité du bestio pour trouver l'endroit où ce qu'il croyait être vrai ne l'était pas.

    Et si c'est évident, raison de plus pour l'affirmer. En tant que relecteur qui ne connait rien au problème voir une taille sortie de nulle part utilisée ailleurs choque. BTW, si l'objectif est de changer le dernier élément de la colonne, un
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    copy_graph[i].back() = k_half;
    suffirait.

    Pour valgrind, il suffit de le lancer et de traiter les problèmes dans l'ordre. Si le programme se lançait avec "./prog param1 -o param2", il suffit de faire "valgrind ./prog param1 -o param2". C'est déjà un bon début (on peut aussi lui dire de s'arrêter à la première erreur rencontrée et de passer en debugage à ce moment là). Mais si c'est bien un problème d'écriture hors bornes (ce que je soupçonne vu que je ne vois pas de trace de pointeur brut dans le code donné), le mode sanatize=address peut être bien plus riche en info.

    Et ne pas négliger la 3e alternative qui consiste à passer la STL en mode checké. J'insiste. Valgrind, tout le monde en parle. Mais ça génère beaucoup de bruit, les contextes ne sont jamais clairs si on ne force pas le debug à la première erreur trouvée, et ça peut être bien trop lent. Alors qu'il y a des outils qui vont faire du failfast et permettre de disposer simplement du contexte lors de l'exécution (typiquement un coredump)
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  5. #5
    Membre confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Par défaut
    Rebonsoir, j'ai commencé par tester ton assert et tu avais raison, ça a pété. Je ne sais pas trop pourquoi sans doute je m'y suis mal pris. Ca ne change pas vraiment la dernière colonne, ça en rajoute une. Donc comme back() ça touche à la dernière colonne existante je crois pas que ça va marcher. Mais merci

  6. #6
    Expert confirmé
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 292
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Août 2003
    Messages : 5 292
    Par défaut
    Pour rajouter une colonne, c'est push_back() alors.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. free(): invalid next size (normal)
    Par Heimdall dans le forum C
    Réponses: 18
    Dernier message: 02/01/2008, 11h25
  2. [JDBC] Erreur très bizarre dans ExecuteQuery
    Par boudou dans le forum JDBC
    Réponses: 6
    Dernier message: 17/03/2006, 18h33
  3. différence reload et location + pb très bizarre pour experts
    Par grinder59 dans le forum Général JavaScript
    Réponses: 21
    Dernier message: 09/01/2006, 12h05
  4. Problème très bizarre avec COUNT
    Par Nomade95000 dans le forum Langage SQL
    Réponses: 4
    Dernier message: 13/10/2005, 14h12
  5. Réponses: 4
    Dernier message: 28/09/2002, 00h00

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo