[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #14, bug #18087 (project freeciv): Oh there is so much stack abuse in freeciv. ...question: is allocating huge arrays on the stack instead of allocating the same arrays on the heap (in the absence of recursion etc) really an abuse? Having read around a bit more, I'm now convinced it's not a good idea. Wikipedia http://en.wikipedia.org/wiki/Stack-based_memory_allocation suggests that a thread's stack size can be as small as a few dozen kilobytes, and more specifically, the Windows documentation http://msdn.microsoft.com/en-us/library/ms686774%28v=vs.85%29.aspx says The default stack reservation size used by the linker is 1 MB. What I think I'd missed with my it's all memory argument is that when memory runs out, malloc() can return NULL (from which the application can theoretically recover), whereas allocating memory on the stack can't fail, so the OS has little option but to kill the entire app. It looks like as a result of that, some (all?) OSes (such as Windows, see previous article) set aside memory for app stacks, so that apps aren't killed for the crime of calling a function when things get tight. Thus stack memory is more reliable than heap memory, thus more precious, thus OSes place limits on it, thus it's not a good idea to try to allocate arbitrarily large chunks of it. Sorry if that was obvious to everyone else. Conclusion is, we shouldn't allocate O(xsize*ysize) memory on the stack. IMO we should take the stack-abuse changes on S2_3, as well as the assign_continent_flood() change that we know we need. I've had a look and they look basically fine to me; more in future comments. ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #15, bug #18087 (project freeciv): Attached my version of file #12960, split into three separate patches and tweaked a little. The three patches: * *trunk-S2_3-hugemap-stack-overflow.diff*: The stack overflow fixes. This is what I propose we apply to S2_3 pre RC1, to deal with bug #17962. _I will do so if there are no objections in 36h._ ** I've reviewed this to check that no memory leaks came in with the introduction of heap allocation due to returning without freeing. I only noticed one: in sg_load_map_known()), SAVE_MAP_CHAR() - sg_failure_ret() - sg_check_ret() can return prematurely. This is a leaky pattern and should be dealt with (raise a ticket), but it's an error condition so I think we can live without a fix for RC1. ** I've only reviewed the existing changes for correctness; I haven't looked to see if there are any map-sized stack allocations that have been missed. ** I haven't reviewed the new flooding algorithm in detail. It looks vaguely plausible. ** As a sanity check, I've played a single-player game with this patch (S2_3) for a few tens of turns without the world ending. No autogame testing yet. * *trunk-S2_3-hugemap-colatitude.diff*: This messes with colatitude stuff I don't fully understand, so it seems riskier to me. Unless someone thinks otherwise, I suggest we leave it out for 2.3.0-RC1, since it's not necessary to fix the stack issues. Could add it back to a later 2.3.x. ** This bit of the patch is Matthias; it came in between file #12942 (comment #4) and file #12947 (comment #5). ** Matthias: do you think this patch is useful/necessary for the map size limits we have on S2_3? * *trunk-S2_3-hugemap-biggermaps.diff*: This actually increases the maximum map sizes. I suggest we leave this for trunk only. ** Aside: I think the correct way to express the relationship between MAP_MAX_SIZE and MAX_DBV_LENGTH is to publish the latter in bitvector.h and have a static (compile-time) assert in the map code. But we don't seem to have a static assert mechanism yet. I may look into it. My tweaks were: * Remove memset()s that were redundant due to use of fc_calloc() * Change free() to FC_FREE() throughout, for form's sake * Add 'const' to constant arrays in smooth_int_map() * Rationalise away 'ret' in rand_map_pos_filtered() (file #13529, file #13530, file #13531) ___ Additional Item Attachment: File name: trunk-S2_3-hugemap-stack-overflow.diff Size:16 KB File name: trunk-S2_3-hugemap-colatitude.diff Size:1 KB File name: trunk-S2_3-hugemap-biggermaps.diff Size:2 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Update of bug #18087 (project freeciv): Assigned to: syntron = jtn Planned Release: 2.4.0 = 2.3.0,2.4.0 ___ Follow-up Comment #13: Stealing ticket, as I'm currently looking at applying most of this to S2_3, to deal with bug #17962 (our last real blocker). I have a slightly cleaned up patch in preparation. I'm inclined not to actually increase the map size limit so close to an RC, given that issues are still coming out of the woodwork for our current limits. I'll do something sensible with the tickets and assign the unfinished business back to syntron for 2.4.0. ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #12, bug #18087 (project freeciv): So we probably want to steal at least some of this patch for 2.3.0 to deal with bug #17962. We'll want at least the recursion fix for assign_continent_flood(). Question is, do we want to be selective about the rest? As far as I can tell on a quick glance, none of it breaks network or savegame compatibility, so it's all about the risk, either. On a quick glance, much of the patch seems to be taking big allocations off the stack and replacing them with calloc/free with exactly the same lifetime... Oh there is so much stack abuse in freeciv. ...question: is allocating huge arrays on the stack instead of allocating the same arrays on the heap (in the absence of recursion etc) really an abuse? Naively, I'd expect them to come out of the same memory, and you can't forget to free an array on the stack. Are there platforms where allocating stack is more likely to fail or generally smellier than allocating heap? (Genuine question; my experience isn't that wide.) ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #11, bug #18087 (project freeciv): the recursive loop in assign_continent_flood() is a problem See also bug #17962 for a case where it causes a problem in unmodified Freeciv. ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #10, bug #18087 (project freeciv): updated patch which keeps savegame compatibility (file #12960) ___ Additional Item Attachment: File name: 0005-allow-map-sizes-up-to-2000x1000.patch Size:20 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #8, bug #18087 (project freeciv): The attached patch should work. Could you please test it and post your results? Bellow the patch describtion is listed: allow map sizes up to 2000x1000 see gna bug #18087 patch by akfaew akfaew and myself * remove old comments * redo assign_countinent_flood (not recursive) * remove MAP_MAX_(HEIGHT|WEIGHT) as it is not used * increase max x/y value to 32*1024 * allocate all variable using MAP_INDEX_SIZE * increase possible map size up to MAP_MAX_SIZE = 2048 (= 2048 * 1000 tiles) * can be increased further; but check also MAX_DBV_LENGTH * possible width/height combinations: 32000x16 or 1000x2000 * fix definition of L_UNIT (could be 0 for big maps = division by zero) * fix savegame2 for bigger maps memory needed for a 32x32000 / a 2000x1000 map with 2 players each (turn 0; with debug; for more players the numbers will increase!): server: approx. 285(385) / 600( 700) MB (no connection) client: approx. 315(540) / 470( 700) MB (gtk; player connected) server: approx. 490(590) / 939(1030) MB (global observer connected) client: approx. 520(740) / 870(1100) MB (gtk; global observer connected) for each line the output of top is used: RES/VIRT network traffic needed to send the map information: large! (several minutes to send all data to a client on the same computer) savegame: 1.7(60) / 0.5(80) MB the compressed and the (uncompressed) size is listed (file #12952) ___ Additional Item Attachment: File name: 0005-allow-map-sizes-up-to-2000x1000.patch Size:29 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #9, bug #18087 (project freeciv): Please discard the format changes to savegame.c (%04d = %05d). It is only a cosmetic change but also creates an incompatible savegame format. I will post an updated patch without it as soon as possible. ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #6, bug #18087 (project freeciv): +#define MAP_MAX_SIZE 4048 Why such a strange number? Shouldn't this be 4096? +#define MAX_DBV_LENGTH (4 * 1024 * 1024) Perhaps 4096 * 1000? ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #7, bug #18087 (project freeciv): +#define MAP_MAX_SIZE 4048 Why such a strange number? Shouldn't this be 4096? You are right; it was 2048 in an earlier test +#define MAX_DBV_LENGTH (4 * 1024 * 1024) Perhaps 4096 * 1000? Also OK; at the moment the temperature map is quit problematic. Furthermore, there seems to be an endless loop. My computer tried for 5 hours to generate a map of size 2000x2000. Memory requirement was at about 700MB but it was not limiting ... ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
Re: [Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Matthias Pfafferodt no-reply.invalid-addr...@gna.org writes: Follow-up Comment #7, bug #18087 (project freeciv): +#define MAP_MAX_SIZE 4048 Why such a strange number? Shouldn't this be 4096? You are right; it was 2048 in an earlier test +#define MAX_DBV_LENGTH (4 * 1024 * 1024) Perhaps 4096 * 1000? Also OK; at the moment the temperature map is quit problematic. Furthermore, there seems to be an endless loop. My computer tried for 5 hours to generate a map of size 2000x2000. Memory requirement was at about 700MB but it was not limiting ... Didn't you run into the problem that detecting continents (flood fill) runs into a stack overflow because it recurses too much? MfG Goswin ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
Re: [Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Quoting Goswin von Brederlow goswin-...@web.de: Matthias Pfafferodt no-reply.invalid-addr...@gna.org writes: Follow-up Comment #7, bug #18087 (project freeciv): +#define MAP_MAX_SIZE 4048 Why such a strange number? Shouldn't this be 4096? You are right; it was 2048 in an earlier test +#define MAX_DBV_LENGTH (4 * 1024 * 1024) Perhaps 4096 * 1000? Also OK; at the moment the temperature map is quit problematic. Furthermore, there seems to be an endless loop. My computer tried for 5 hours to generate a map of size 2000x2000. Memory requirement was at about 700MB but it was not limiting ... Didn't you run into the problem that detecting continents (flood fill) runs into a stack overflow because it recurses too much? NO; this was fixed. The version of this function in the patch does not use recursion at all but a combination of a while loop and a tile list. Matthias (aka syntron) MfG Goswin This message was sent using IMP, the Internet Messaging Program. ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Update of bug #18087 (project freeciv): Category:None = general Assigned to:None = syntron Planned Release: = 2.4.0 ___ Follow-up Comment #4: Here is my first try one the problem. As you found out the recursive loop in assign_continent_flood() is a problem. I do it in one while loop. Furthermore, there are problem with smooth_int_map(). At the moment maps up to at least 2000x200 are possible. The memory requirement are: server 2000x200 map 20 players turn 0: 600MB client global observer: 450MB So why isn't it defined to be MAP_MAX_SIZE * 1000? And is this define really necessary? These are the only occurrences: MAX_DBV_LENGTH gives the largest size of a dynamic bit vector (dbv). MAP_MAX_SIZE can't be used as this value is not available for files in ./utilities. (file #12942) ___ Additional Item Attachment: File name: 0009-allow-map-sizes-up-to-2048x200.patch Size:5 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #5, bug #18087 (project freeciv): and the next try ... could you test it with the scenario? A 32000x16 map can be created but for larger y sizes as well as for maps 400.000 the map generator seems to have problems. (file #12947) ___ Additional Item Attachment: File name: big_map.diff Size:17 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Nachricht geschickt von/durch Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #1, bug #18087 (project freeciv): Oh there is so much stack abuse in freeciv. Is it OK if I post patch to each file as a separate diff and message? (file #12933) ___ Additional Item Attachment: File name: startpos.c.diffSize:0 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #2, bug #18087 (project freeciv): The problem with my previous patch is that it will take up that space forever, which is also wrong. I think this needs to be done with malloc and free. I won't continue with this today and will wait for some feedback. Disregard startpos.c.diff please. [MAP_INDEX_SIZE] found in ./server/score.c: 162: bv_player claims[MAP_INDEX_SIZE]; [MAP_INDEX_SIZE] found in ./server/savegame2.c: 2763: int known[lines][MAP_INDEX_SIZE], j, p, l; 2815: int known[lines][MAP_INDEX_SIZE], j, l, p; [MAP_INDEX_SIZE] found in ./server/savegame.c: 1296: int known[MAP_INDEX_SIZE]; 1536: int known[MAP_INDEX_SIZE]; [MAP_INDEX_SIZE] found in ./server/generator/startpos.c: 206: int tile_value_aux[MAP_INDEX_SIZE]; 207: int tile_value[MAP_INDEX_SIZE]; [MAP_INDEX_SIZE] found in ./server/generator/utilities.c: 193: int alt_int_map[MAP_INDEX_SIZE]; [MAP_INDEX_SIZE] found in ./server/advisors/autosettlers.c: 622: struct settlermap state[MAP_INDEX_SIZE]; [MAP_INDEX_SIZE] found in ./common/map.c: 1081: int count = 0, positions[MAP_INDEX_SIZE]; ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
[Freeciv-Dev] [bug #18087] server segfault on a map with 1.3M tiles
Follow-up Comment #3, bug #18087 (project freeciv): The attached patch manages to get me thru the segfaults. (It's a cat of small diffs, gna only allows max 4 uploads) Now there are problems with assertions: 1: in dbv_init() [bitvector.c::57]: assertion 'bits 0 bits 512 * 1024' failed. 1: Please report this message at http://gna.org/projects/freeciv/ /* Maximal size of a dynamic bitvector; for the map known bitvector it must be larger than the biggest possible map size (approx. MAP_MAX_SIZE * 1000) Use a large value to be on the save side (512kbits = 64kb). */ #define MAX_DBV_LENGTH 512 * 1024 So why isn't it defined to be MAP_MAX_SIZE * 1000? And is this define really necessary? These are the only occurrences: ./utility/bitvector.c:#define MAX_DBV_LENGTH 512 * 1024 ./utility/bitvector.c: than 0 and lower than the maximal size given by MAX_DBV_LENGTH. The ./utility/bitvector.c: fc_assert_ret(bits 0 bits MAX_DBV_LENGTH); ./utility/bitvector.c: fc_assert_ret(bits 0 bits MAX_DBV_LENGTH); I bumped it (and fixed a potential bug): -#define MAX_DBV_LENGTH 512 * 1024 +#define MAX_DBV_LENGTH (2048 * 1024) I call this win, because now my server is killed by the OS because of lack of memory :) The server allocated 400MB and client 200MB before being killed. (file #12935) ___ Additional Item Attachment: File name: diff Size:9 KB ___ Reply to this item at: http://gna.org/bugs/?18087 ___ Message sent via/by Gna! http://gna.org/ ___ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev
