[Libvir] [PATCH] Fix the function that remove the element of the hash table.
There are two logic error and a unnecessary else-statement in virHashRemoveSet function. This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements. (3/3) Unnecessary else-statement. (1/3) The logic error that use released memory area. This bug causes the crash of virt-manager or virsh. If "virsh undefine" command is executed, "Segmentation Fault" is caused. The result of executing "valgrind virsh" command is: virsh # list --all ==3337== Invalid read of size 4 ==3337== at 0x4016A21: virHashRemoveSet (hash.c:562) ==3337== by 0x403ACF4: xenXMConfigCacheRefresh (xm_internal.c:458) ==3337== by 0x4040D58: xenXMNumOfDefinedDomains (xm_internal.c:2518) ==3337== by 0x40245C3: xenUnifiedNumOfDefinedDomains (xen_unified.c:1004) ==3337== by 0x4013730: virConnectNumOfDefinedDomains (libvirt.c:2446) ==3337== by 0x804AE81: cmdList (virsh.c:577) ==3337== by 0x8052E6E: vshCommandRun (virsh.c:4052) ==3337== by 0x8054E2D: main (virsh.c:5036) ==3337== Address 0x4282AB8 is 0 bytes inside a block of size 16 free'd ==3337== at 0x4004FDA: free (vg_replace_malloc.c:233) ==3337== by 0x40169A0: virHashRemoveSet (hash.c:545) ==3337== by 0x403ACF4: xenXMConfigCacheRefresh (xm_internal.c:458) ==3337== by 0x4040D58: xenXMNumOfDefinedDomains (xm_internal.c:2518) ==3337== by 0x40245C3: xenUnifiedNumOfDefinedDomains (xen_unified.c:1004) ==3337== by 0x4013730: virConnectNumOfDefinedDomains (libvirt.c:2446) ==3337== by 0x804AE81: cmdList (virsh.c:577) ==3337== by 0x8052E6E: vshCommandRun (virsh.c:4052) ==3337== by 0x8054E2D: main (virsh.c:5036) The current removing logic is: 1. search for node that be removed in the hash table. The removing cursor(pointer) point to "element-B". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-A |-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+ 2. free "element-B". The removing cursor point to invalid address +-hash table---+ | +----------+ | +----------+ | |element-A |-|-->|element-C | | +----------+ | +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+ 3. try to move the removing cursor to next node. At this time, the error occurs. (2/3) The logic error that doesn't remove elements. The current removing logic is: 1. search for node that will be removed in the hash table. The removing cursor point to "element-A". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-A |-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+ 2. copy "element-B" to "element-A". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-B'|-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+ 3. remove "element-B" The removing cursor point to "element-D". "element-C" is skipped. +-hash table---+ | +----------+ | +----------+ | |element-B'|-|-->|element-C | | +----------+ | +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+ (3/3) Unnecessary else-statement. There is else-statement that set NULL to the NULL pointer. Thanks, Hiroyuki Kaguchi Index: hash.c =================================================================== RCS file: /data/cvs/libvirt/src/hash.c,v retrieving revision 1.27 diff -u -r1.27 hash.c --- hash.c 21 Jan 2008 16:29:10 -0000 1.27 +++ hash.c 28 Jan 2008 06:48:09 -0000 @@ -543,6 +543,7 @@ if (prev) { prev->next = entry->next; free(entry); + entry = prev; } else { if (entry->next == NULL) { entry->valid = 0; @@ -553,6 +554,7 @@ sizeof(virHashEntry)); free(entry); entry = NULL; + i--; } } table->nbElems--; @@ -560,8 +562,6 @@ prev = entry; if (entry) { entry = entry->next; - } else { - entry = NULL; } } }
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements. (3/3) Unnecessary else-statement.
Index: hash.c =================================================================== RCS file: /data/cvs/libvirt/src/hash.c,v retrieving revision 1.27 diff -u -r1.27 hash.c --- hash.c 21 Jan 2008 16:29:10 -0000 1.27 +++ hash.c 28 Jan 2008 06:48:09 -0000 @@ -543,6 +543,7 @@ if (prev) { prev->next = entry->next; free(entry); + entry = prev; } else { if (entry->next == NULL) { entry->valid = 0;
ACK, this is definitely needed.
@@ -553,6 +554,7 @@ sizeof(virHashEntry)); free(entry); entry = NULL; + i--; } } table->nbElems--;
I'm still not 100% clear on the logic around here, but I think your suggestion is correct.
@@ -560,8 +562,6 @@ prev = entry; if (entry) { entry = entry->next; - } else { - entry = NULL; } } }
ACK, clearly correct. Dan. -- |=- Red Hat, Engineering, Emerging Technologies, Boston. +1 978 392 2496 -=| |=- Perl modules: http://search.cpan.org/~danberr/ -=| |=- Projects: http://freshmeat.net/~danielpb/ -=| |=- GnuPG: 7D3B9505 F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 -=|
Though this patch has not been applied yet, are there any problems in this patch? If there is no problem, could you apply this patch ? (2008/01/29 23:45), Daniel P. Berrange wrote:
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements. (3/3) Unnecessary else-statement.
Index: hash.c =================================================================== RCS file: /data/cvs/libvirt/src/hash.c,v retrieving revision 1.27 diff -u -r1.27 hash.c --- hash.c 21 Jan 2008 16:29:10 -0000 1.27 +++ hash.c 28 Jan 2008 06:48:09 -0000 @@ -543,6 +543,7 @@ if (prev) { prev->next = entry->next; free(entry); + entry = prev; } else { if (entry->next == NULL) { entry->valid = 0;
ACK, this is definitely needed.
@@ -553,6 +554,7 @@ sizeof(virHashEntry)); free(entry); entry = NULL; + i--; } } table->nbElems--;
I'm still not 100% clear on the logic around here, but I think your suggestion is correct.
@@ -560,8 +562,6 @@ prev = entry; if (entry) { entry = entry->next; - } else { - entry = NULL; } } }
ACK, clearly correct.
Dan.
Hiroyuki Kaguchi <fj7025cf@aa.jp.fujitsu.com> wrote:
Though this patch has not been applied yet, are there any problems in this patch? If there is no problem, could you apply this patch ?
(2008/01/29 23:45), Daniel P. Berrange wrote:
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements.
Considering your analysis, I'm sure there's no problem. However, it would be far easier to accept if we could easily demonstrate the failures. Can you provide a stand-alone test case that provokes #1 and #2? Ideally, it would be in the form of a main program that initializes a hash table, performs some inserts and then performs the offending deletion. Bonus points if you also add a test case (run by "make check") that fails before your patch and passes once it's applied.
(3/3) Unnecessary else-statement.
The reappearance procedures: #1 The logic error that use released memory area. 1. define two or more domains which are same hash key. (ex. the domain names are "domain_01" and "domain_28") 2. execute virsh by interactive mode 3. execute "list --all" command. 4. undefine a domain on another session. (ex. undefine domain_28) 5. execute "list --all" command. Segmentation Fault occur. #2 The logic error that doesn't remove elements. 1. define two or more domains which are same hash key. 2. execute virsh by interactive mode 3. execute "list --all" command. 4. undefine the defined domains on another session. 5. execute "list --all" command. A domain is not removed from the list during the fixed time(10sec). On 2008/02/06 17:38, Jim Meyering wrote:
Hiroyuki Kaguchi <fj7025cf@aa.jp.fujitsu.com> wrote:
Though this patch has not been applied yet, are there any problems in this patch? If there is no problem, could you apply this patch ?
(2008/01/29 23:45), Daniel P. Berrange wrote:
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements.
Considering your analysis, I'm sure there's no problem. However, it would be far easier to accept if we could easily demonstrate the failures. Can you provide a stand-alone test case that provokes #1 and #2?
Ideally, it would be in the form of a main program that initializes a hash table, performs some inserts and then performs the offending deletion.
Bonus points if you also add a test case (run by "make check") that fails before your patch and passes once it's applied.
(3/3) Unnecessary else-statement.
On Tue, Jan 29, 2008 at 02:45:44PM +0000, Daniel P. Berrange wrote:
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements. (3/3) Unnecessary else-statement.
Okay, I checked that fnction is actually not coming from libxml2 it was derived from the existing call which removes a single element and doesn't suffer the problem.
Index: hash.c =================================================================== RCS file: /data/cvs/libvirt/src/hash.c,v retrieving revision 1.27 diff -u -r1.27 hash.c --- hash.c 21 Jan 2008 16:29:10 -0000 1.27 +++ hash.c 28 Jan 2008 06:48:09 -0000 @@ -543,6 +543,7 @@ if (prev) { prev->next = entry->next; free(entry); + entry = prev; } else { if (entry->next == NULL) { entry->valid = 0;
ACK, this is definitely needed.
Agreed,
@@ -553,6 +554,7 @@ sizeof(virHashEntry)); free(entry); entry = NULL; + i--; } } table->nbElems--;
I'm still not 100% clear on the logic around here, but I think your suggestion is correct.
Yes, that's right, we are suppressing the first entry in the clash list, and one way to continue exploring other entries in the list is to set entry to NULL and decreasing the index. Note that it could go to -1 until it reaches the outer loop where it will be increased again to 0, so it's kind of nasty, but this works. Instead I changed the patch slightly to avoid this, move table->nbElems-- before the unlinking, and then setting entry back to the first element of the list, and issuing a continue to reenter the while (entry && entry->valid) this is cleaner, more local, and avoid the -1 value for i.
@@ -560,8 +562,6 @@ prev = entry; if (entry) { entry = entry->next; - } else { - entry = NULL; } } }
ACK, clearly correct.
yes that's superfluous. I end up with the following patch, I will commit this shortly, thanks ! Daniel -- Red Hat Virtualization group http://redhat.com/virtualization/ Daniel Veillard | virtualization library http://libvirt.org/ veillard@redhat.com | libxml GNOME XML XSLT toolkit http://xmlsoft.org/ http://veillard.com/ | Rpmfind RPM search engine http://rpmfind.net/
On Tue, Jan 29, 2008 at 11:32:04AM +0900, Hiroyuki Kaguchi wrote:
There are two logic error and a unnecessary else-statement in virHashRemoveSet function.
Hum, I will have to double check, I cleaned up something in libxml2 recently which may have been similar.
This patch fix the following. (1/3) The logic error that use released memory area. (2/3) The logic error that doesn't remove elements. (3/3) Unnecessary else-statement.
(1/3) The logic error that use released memory area. This bug causes the crash of virt-manager or virsh. If "virsh undefine" command is executed, "Segmentation Fault" is caused.
The result of executing "valgrind virsh" command is: virsh # list --all ==3337== Invalid read of size 4 ==3337== at 0x4016A21: virHashRemoveSet (hash.c:562) ==3337== by 0x403ACF4: xenXMConfigCacheRefresh (xm_internal.c:458) ==3337== by 0x4040D58: xenXMNumOfDefinedDomains (xm_internal.c:2518) ==3337== by 0x40245C3: xenUnifiedNumOfDefinedDomains (xen_unified.c:1004) ==3337== by 0x4013730: virConnectNumOfDefinedDomains (libvirt.c:2446) ==3337== by 0x804AE81: cmdList (virsh.c:577) ==3337== by 0x8052E6E: vshCommandRun (virsh.c:4052) ==3337== by 0x8054E2D: main (virsh.c:5036) ==3337== Address 0x4282AB8 is 0 bytes inside a block of size 16 free'd ==3337== at 0x4004FDA: free (vg_replace_malloc.c:233) ==3337== by 0x40169A0: virHashRemoveSet (hash.c:545) ==3337== by 0x403ACF4: xenXMConfigCacheRefresh (xm_internal.c:458) ==3337== by 0x4040D58: xenXMNumOfDefinedDomains (xm_internal.c:2518) ==3337== by 0x40245C3: xenUnifiedNumOfDefinedDomains (xen_unified.c:1004) ==3337== by 0x4013730: virConnectNumOfDefinedDomains (libvirt.c:2446) ==3337== by 0x804AE81: cmdList (virsh.c:577) ==3337== by 0x8052E6E: vshCommandRun (virsh.c:4052) ==3337== by 0x8054E2D: main (virsh.c:5036)
The current removing logic is: 1. search for node that be removed in the hash table. The removing cursor(pointer) point to "element-B". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-A |-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+
2. free "element-B". The removing cursor point to invalid address +-hash table---+ | +----------+ | +----------+ | |element-A |-|-->|element-C | | +----------+ | +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+
3. try to move the removing cursor to next node. At this time, the error occurs.
(2/3) The logic error that doesn't remove elements.
The current removing logic is: 1. search for node that will be removed in the hash table. The removing cursor point to "element-A". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-A |-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+
2. copy "element-B" to "element-A". +-hash table---+ | +----------+ | +----------+ +----------+ | |element-B'|-|-->|element-B |-->|element-C | | +----------+ | +----------+ +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+
3. remove "element-B" The removing cursor point to "element-D". "element-C" is skipped. +-hash table---+ | +----------+ | +----------+ | |element-B'|-|-->|element-C | | +----------+ | +----------+ | |element-D | | | +----------+ | | . | | . | +--------------+
(3/3) Unnecessary else-statement. There is else-statement that set NULL to the NULL pointer.
Thanks, Hiroyuki Kaguchi
Index: hash.c =================================================================== RCS file: /data/cvs/libvirt/src/hash.c,v retrieving revision 1.27 diff -u -r1.27 hash.c --- hash.c 21 Jan 2008 16:29:10 -0000 1.27 +++ hash.c 28 Jan 2008 06:48:09 -0000 @@ -543,6 +543,7 @@ if (prev) { prev->next = entry->next; free(entry); + entry = prev; } else { if (entry->next == NULL) { entry->valid = 0; @@ -553,6 +554,7 @@ sizeof(virHashEntry)); free(entry); entry = NULL; + i--; } } table->nbElems--; @@ -560,8 +562,6 @@ prev = entry; if (entry) { entry = entry->next; - } else { - entry = NULL; } } }
-- Libvir-list mailing list Libvir-list@redhat.com https://www.redhat.com/mailman/listinfo/libvir-list
-- Red Hat Virtualization group http://redhat.com/virtualization/ Daniel Veillard | virtualization library http://libvirt.org/ veillard@redhat.com | libxml GNOME XML XSLT toolkit http://xmlsoft.org/ http://veillard.com/ | Rpmfind RPM search engine http://rpmfind.net/
participants (4)
-
Daniel P. Berrange -
Daniel Veillard -
Hiroyuki Kaguchi -
Jim Meyering