samothMember Since 18 Jan 2008
Offline Last Active Today, 06:49 AM
- Group Crossbones+
- Active Posts 3,298
- Profile Views 16,570
- Submitted Links 0
- Member Title Member
- Age Age Unknown
- Birthday Birthday Unknown
Posted by samoth on 25 June 2016 - 03:24 AM
Which can happen for a variety of reasons (no symbols present being one, third party module being another, with GCC inlined functions can be tricky, too, since GCC can actually optimize in debug mode).
Normally, the debugger will try its best to tell you the name of the function, and the source code line, and where it was called from, and so on. It does that by looking at the return addresses on the stack, and trying to translate them to something readable one by one.
Posted by samoth on 23 June 2016 - 06:45 AM
every index starts on zero
Yes it does. But your code effectively looks like this:
1. set vector to have exactly 100 elements 2. whenever XYZ, do the following increment i, don't care what value it has take address of vector[i], don't care whether it's outside bounds pass address to another thread, write to it now that it's too late, check whether (i == 100), and let it wrap to -1 3. repeat at (2)
It's correct that the index starts at zero, but it reaches a value (100) which is out of bounds. Valid indices go from 0 to 99, not 100. readdata is equivalent to readdata.end(), and the standard defines dereferencing end() as undefined behavior.
I don't have time to thoroughly read through your new code, but this here again smells of trouble:
Not only is this not terribly efficient (unlike reserve, resize will not grow geometrically, but will do exactly as you say, so resizing to 101, 102, 103, and 104 will do 4 reallocations and deep copies!). But more urgently, resizing will -- almost guaranteed -- change the address of the vector's backing storage, and thus pointers which are still being held in one of your writing threads will be invalid. What's bad is that you cannot even rely on the fact that the addresses you're writing to are invalid. Depending on how the container and the CRT manage memory, they might be "valid", that is, it might seem to "work" although the code is completely wrong. This is a recipe for desaster.
Posted by samoth on 22 June 2016 - 04:22 AM
The "next to no protection" bit is not so much an issue because finally you cannot prevent someone from stealing your stuff anyway if the data plus the executable that can decrypt said data is on their harddisk. You can make it somewhat harder, and that's it. But DES is slow in addition to that, and that makes it a bad candidate.
I'm using XOR-encryption on a simple (non-secure) pseudorandom generator. That's about as fast as memcpy, and admittedly not very secure, but it stops the most obvious stupid attempts of unsavy people looking into, or tampering with datafiles (even more so as datafiles are compressed). As stated above, you cannot do this securely anyway, that's wasted time. To anyone not knowing the trade, this is a showstopper, and that's the intent. To anyone with the least bit of experience, it's laughable. Annoying, but pretty much as good as you can get, unless you control the hardware.
XOR-encryption is mighty fine, really. You don't even need a particularly clever, or even "random" random generator. Anything that is not immediately obvious and already implemented in editors with a plugin or script (like ROT13) and that prevents identical input values from having the same identical output values every time will do. Just enough so you cannot see patterns with the naked eye and so you can't select "un-ROT13" from the editor's menu to get something readable.
If you are in super paranoia mode, you could use a simple and fast Feistel cipher like TEA (need not even bother with the improved versions, and even half the number of rounds will do). A few lines of portable code, no huge state, and fast. And... totally sufficient.
The advantage of a block cipher over a stream cipher is that changing one byte always changes the entire output block. That makes byte-tampering with a hex editor even harder since you don't just change one byte but e.g. 16 of them at a time. But the problem of tampering is solved better with a checksum. Of course, with a checksum, you have the same issue again. It's stored on the user's computer, so the total amount of security that you can achieve is... somewhat limited. But you can sure make the life of someone trying to change a wall texture ID to transparent somewhat harder.
The bad news is, computer security is like dying due to being struck by lightning. Unless you are a total idiot, and if you take minimum precautions (such as not going on an open field with a metal rod in your hands during a thunderstorm), getting struck by lightning is an extremely difficult task. It's so rare it doesn't happen once in a lifetime. But when it happens... it literally happens once in a lifetime. Once is enough.
Encryption safely prevents a hundred million unsavy users from accessing something you don't want them to read, and the chance that they find a way are very small. But once is enough. If one dedicated (and skilled) person finds a way, the next day the 99.9 million remaining people will use the same click-to-crack patcher. And unluckily, there's more than just one person out there with spare time to try and nothing better to do, too.
Posted by samoth on 21 June 2016 - 05:59 PM
If this is all the code, that even works. Well... "works".
I'm not sure how you expect that to work? What's stopping the vector from being resized (and thus any addresses pointing into it now potentially pointing to invalid memory) while your other thread is reading from it?
The vector is not being resized, its size is set to 100 once, and I think that is just the problem. The code increments a counter, then takes the ith element's address and passes it to another thread which writes to that address. And then, only then, it checks whether the index is 100. That's a simple out of bounds write. Plus, setting the index to -1 will be another one.
To spice it up, half of the code is lambdas and the thread is launched from a thread object which is a member that is initalized with a capture-all-by-ref lambda (I didn't even know this was legal at class scope!), plus every single lambda captures all by ref, even though none seems to using any of that. It sure makes reading the code more of an adventure (an adventure of the "did I miss something?" kind).
Posted by samoth on 21 June 2016 - 07:53 AM
I agree. It is without any doubt possible, but the question should really be "does it make sense, is it the best thing?".
Personally I think you shouldn't use the octree as a pathing graph and instead should create a more appropriate graph.
Pushing back the question wheter an octree is very suitable at all for a moment...
Do you strictly need 3D pathfinding at all? Most people do well enough with "2D and some", and not few even only do 2D at all (without the "and some"). Plain 2D is sometimes a bit poor with flying units that cannot cross water and such, but still "and some" is normally good enough, you rarely need real 3D. Adding a node that is for flying units only usually does the trick. Most units don't move in 3D anyway, and if they do, they don't truly move in 3D if you take the ground as a reference, or hardly.
The only things I could ad hoc think of that really need true 3D pathfinding would be a dungeon maze with several levels, aerial combat simulation, or space games. Everything else either walks on the ground, or has some flying abilities, but still mostly-walks-on-ground for practical purposes.
Mazes are not normally large enough to justify an octree. Also, in a maze, agents usually don't need to pathfind from the bottom to the top. It's the player's task to do that, and monsters are usually per-level 2D beasts... If monsters are able to track the player up the next stairway, that's already almost revolutionary (how many games do that!) -- and this can be easily done with one extra node over the stairway.
Airplanes really only need to care about not flying into a mountain or tower, the rest is more or less "straight line through mostly empty space", so that would be "2D plus". Shoot at enemy airplane? Draw a line.
Yes, in real life you have flight levels and corridors, but that's a different thing, and it isn't a pathfinding problem either. There's a well-defined course and altitude which you must follow, and you have no questions to ask or think of a better route (flight control tells you exactly what to do).
Similar for space sim. Most of the universe is empty, and "draw a straight line" works 99% fine. And when it doesn't work, you just have to "bend" your path ever so little so you don't fly through a star. So basically, draw a straight line, and see if it collides with the bounding sphere of something of planetar size. Unless you want something like navigate fully automatically through a narrow passage between two hostile territories, I don't see how there's large demands on path finding there.
There's that "hierarchical pathfinding" thing of course, or the "hierarchical AI" thing in general. Which has its merits. But an octree (or let's say quadtree) still doesn't seem like the necessarily best approach. I'm using a "somewhat hierarchical" regular grid representation for the world myself (with three levels alltogether) because I like the idea that you can just stop simulating what no player can see, and I'm cheap. But pathfinding itself is in fact embarrassingly poor, yet it works entirely satisfyingly (indeed, it being poor accounts for the fact that units are not omniscient, which is desired).
That hierarchic stuff is not a free lunch alltogether anyway, there is a point where things turn around, and it's hard to predict where and when. After finding a path within high-level nodes, you still have to pathfind within each high-level node, and if these are huge, they contain a lot of child (grand child, grand-grand child, ...) nodes, which are added to the sub-search again. It still prunes a lot away, but it's not a free lunch alltogether, and infinitely. Plus, unless you put a lot of extra work into it, there is a good chance of getting a rather sub-optimal path (which is not always undesirable, more perfect is not always more good).
I haven't ever tried the octree approach, so everything here is just guesstimate. But the mere added complexity paired with the uncertainity whether it really adds a lot turns me away.
There's that thing called cache, too. Octrees are one of those structures which look awesome, and perform awesome -- on paper, looking at complexity numbers, and also in some real-life situations. And then they fail miserably in other situations, solely because the way you access them doesn't play well with the hardware. There are some access patterns (and I am afraid A* might exactly be one of them!) which are catastrophic worst-case to an octree (unless the whole octree fits into cache, and in that case it's so small that it's pointless).
I remember (unrelated to pathfinding) an article some 4-5 years ago analyzing Minecraft-like engines which concluded that although octree is what everybody intuitively jumps onto, it fails performance-wise because of iteration being the main operation.
Posted by samoth on 21 June 2016 - 03:43 AM
I'm asking because "segfault" in the same sentence as "lambda" smells like lambda with capture with a reference-to-local or pointer-to-local passed to a callback function (or something similar).
Unluckily, gdb does not show lambda captures in its output, so without knowing the code it's all guessing.
Posted by samoth on 17 June 2016 - 03:18 AM
That does not necessarily mean that execution takes place concurrently to the main thread or concurrently to any other async functions. Strictly speaking, it is legal for std::async to synchronously call the function when you call wait() -- which does stall the program's flow.
Indeed that is a good thing, too.
Naively throwing a sheer infinite number of threads at a problem is almost never a good solution (it works on a GPU, which is explicitly made for that purpose), and it often reduces performance rather than improve it. Context switches and caches are two things to think of here, but also thread creation if you do not pull them from a pool.
A good implementation of std::async would arguably work off its functions from a queue using a pool of workers at a concurrency level less than number-of-cores. But you don't havea a guarantee for that, it might as well simply spawn a thread every time, it might spawn one extra thread regardless of how many tasks there are, or it might execute inside wait(), or any other combination.
Posted by samoth on 16 June 2016 - 07:09 AM
Sure about that? If I recall correctly from what I understood in Kemen's paper, the issue with float depth buffers is exactly that they have far too many bits for very close range, and the curve then goes upwards far too steep, hitting the "useless" area or what he called it after some few hundred meters. His solution works for hundreds/thousands of kilometers (while still being able to discriminate close-up stuff with somewhat reasonable accuracy).
But the old logarithmic or linear depth buffers hacks aren't a useful idea any more. They come with performance overheads and introduce rendering artefacts. You can get the same quality improvement by simply using a floating point depth buffer format instead of a traditional integer/fixed point format (floats have logarithmic precision by design).
Why? ROP is a bottleneck (it's the slowest growing GPU resource). Admittedly, in a space simulation most of the screen is "empty" unless a big planet is in front of you, but still... why throw twice the amount of work at ROP for the areas where there are planets? Normally the skybox is always what you draw last.
-first render the skybox (stars)
(Well no... transparent stuff is what you draw last)
Posted by samoth on 13 June 2016 - 06:22 AM
So after months, I've finally had enough of GCC telling me:
warning: attempt to free a non-heap object 'x' [-Wfree-nonheap-object]
on one particular class whenever it's used anywhere. That's 6 or 7 warnings on an otherwise warning-free program.
What a piece of shit. I am not attempting to free a non-heap object, why does it keep insisting. I'm checking whether the pointer points to a static or dynamically allocated block before I attempt to delete it: if(is_dynamic()).
Besides, if I was really deleting a non-heap object by accident, the program would crash, and I've had this warning for months without ever anything going wrong.
Warnings really annoy me, especially when they're wrong. A correct, well-written program should compile with zero warnings. So, since the compiler is warning on something that's perfectly correct, I have no choice. I'm pulling the relevant lines into a SSCCE in order to submit a bug report, and then I'll just turn the warning off.
Well, you can figure... Looking at the SSCCE, it turns out the compiler was right. Duh.
The function is_dynamic() reads:
return (ptr == local);
when it should obviously be:
return (ptr != local);
Now this sucks on so many levels, it's hard to even list them all
- I made a really dumb typo (OK, that happens)
- The function is_dynamic() which contains the erroneous code exists solely for the purpose of making code more idiomatic and avoiding such mistakes.
- The compiler noticed, and warned about it. I didn't ignore the warning, but looked into it, and found the compiler was wrong.
- I was going to turn the warning off.
- I leaked every time I should have deleted, and I deleted every time I shouldn't. Systematically, not just in one place.
- Everything "worked fine" for months
I'm not sure which one is worst, but I'm inclined to say it's the fact that it "works fine" anyway. Heck, it would probably have "worked" another ten years without anyone noticing.
On a related note: It has been my opinion for a long time that the feature that delete nullptr is well-defined and a no-op (as is free(NULL)) is a mis-feature because it hides program errors. That's a somewhat similar situation. Everything "works fine" even if ownership and object lifetime is unclear, unknown, or wrong. But "works fine" is really not a good thing here, it's a bad thing.
Posted by samoth on 09 June 2016 - 03:41 AM
That hypnotic animated picture is awesome!
Randomly reassigning end-nodes to the secondary hosts will make matching IP addresses with avatars harder, but not impossible. Additionally, as a secondary host, I now do not only know some other users' addresses, but all of them. I can time round trip times to get a rough idea of where they are, too (... or just look in a geo-IP database).
So there is that guy from Denver who always beats me in PvP and boasts about it on the forums. Look, this IP address is located in Denver. Let's see how well he fares with a bit error in every 8th packet received...
But more importantly, you will face some additional hurdles doing so. Those are hurles you create, it doesn't even need a malicious user.
First, this means that you must geolocate the secondary nodes and rotate end nodes only between secondary notes which are close to them. Otherwise, you get unpredictably changing round trip times all the time. 15ms now, and 150ms the next instant because you're rotated to a secondary node in Moscow. That doesn't go well.
In a "static" topology, an end node may be unlucky with its peer, but it has the possibility of saying "this doesn't work, my ping sucks", and be assigned to another (static) peer which is closer or has a more favourable route, or whatever. It's not 100% foolproof, but it works. If secondary peers rotate, this gets a lot more complicated.
Second, there's that nuisance called stateful firewall. Which is what you find in practically every home user's router. You have to do a little dance for inbound datagrams to make it through stateful firewalls. With the same static peers, that's easy, you punch through once and be done. The firewall assumes a "connection" (where there really isn't one) and lets the traffic through. As long as data keeps coming in regularly, all is well.
With constantly rotating peers, you are in a bit of home-made trouble here. Not only are there a lot more peers, so you gotta do a lot more punching. But more importantly, chances are that if a rotation takes long enough, the stateful firewall will time out your "connection". How do you know? Well, you don't, other than packets are suddenly being silently dropped.
Or maybe the stateful firewall will only remember up to a hard total number (say, 5) of connections. If you have 8 rotating secondary nodes and a router which remembers 5, this fails.
Granted, 5 is unrealistically low, let's say 50 connections, then it fails as soon as you have 51 rotating peers. 51 secondary peers is only 408 concurrent players, so that is not very remote. Mind you, we are talking "massive multiplayer", which is more like 40,000. That would be 5,000 rotating secondary notes. I'm pretty sure the majority of stateful firewalls on home user routers will show you the middle finger on that one.
Posted by samoth on 08 June 2016 - 03:18 AM
All other issues (mostly extra latency and reliability) aside... have you thought thoroughly whether you want to have one player know his competiting players' IP addresses? I'm inclined to say: No, you don't want that to happen.
What prevents me from holding back messages for a few dozen milliseconds (just long enough so no NACKs are triggered) and to watch on chat who is typing "lagggggg..." so I have a good chance of knowing exactly which avatar belongs to which IP address? You can encrypt all packets so I don't know what's inside, but now I still know who the packets are for.
What prevents me from selectively dropping them whenever I'm engaged in a PvP challenge with these? What prevents me from SSHing into a server located at university and running a bandwidth tester on that IP address?
What prevents me from randomly flipping a bit in critical situation? Sure, the checksum will detect them, and the client will NACK and trigger a resend (if I am so kind to deliver it, maybe I'll stall the packet again for an extra 5-10ms) but it will add at least one full RTT of delay in the most shitty situation imaginable, probably getting the other guy killed. And it's entirely innocent and unsuspicious. You probably can't even find evidence that I am cheating -- bit errors happen, eh?
And then, there's people playing via WiFi in an internet cafe. Or worse, via LTE. Say that in one sentence with "peer to peer" and "realtime". I don't know what your LTE infrastructure looks like, but I can tell you what Telekom's looks like over here. Mighty fine bandwidth, no doubt, but latency is... holy shit. Like 120+ ms to hosts in the same city.
Posted by samoth on 06 June 2016 - 04:15 AM
Send an UDP datagram out as soon as the user presses the button. If tampered client cheating isn't a concern, send another one 50ms later (but do include a "this is a resend" bit) just for the odd case that the packet got lost. That shouldn't happen anyway, but you never know. If a resend packet is received but no original, assume the original packet being 50ms earlier. Again, this works only under the assumption "no tampered clients".
The first datagram to be received on the server wins. Done.
That's not perfect, but it is pretty much as good as you can get. Everything else which is a lot more complicated isn' really much better.
Synchronized clocks suck. Synchronized high resolution clocks suck a lot. Synchronization and wireless in the same sentence sucks even more. I would want to avoid any such thing if I had any chance.
Posted by samoth on 30 May 2016 - 08:21 AM
In short, yes. Expect trouble.
The first thing is asking for trouble, in particular because you not only copied the tell-tale design, but even call the swords "Ryuko" swords so even people who do not immediately recognize it have no trouble finding it on Google. You can bet the owners of that, what's it hentai, anime (?) will surely get aware. If you are lucky they don't care, but the vast majority of IP owners does care.
You were cautious enough not to call the lightsabers by their name (you call them laser sable), but Star Wars is owned by Disney now, and they are most certainly a company you do not want to test for being forgiving on IP issues. Using a Disney-owned element that can justifiably be seen as "product identity" is outright crazy.
For the second thing, Mario... well, that's Nintendo. This is even more crazy.
Posted by samoth on 30 May 2016 - 05:58 AM
The annoying thing with SO_LINGER is that it is a parade example of a total API and documentation fuckup. It is impossible to understand what it is or what it does, what the purpose is, or what you can use it for, unless you already know.
The name suggests that if you set the connection to linger, then doing something with the socket (closing, to be precise) will cause your application to block for some time. Since you have to do something for that to happen, this is obviously not the default behaviour, or so you should believe.
Microsoft is maximally obscure about what goes on in their implementation, as usual. It merely says "specifies whether a socket should remain open for some time", which doesn't tell us anything about whether the call to closesocket() will block or not. The wording "after a closesocket call" in the Remarks section, however, suggests that the close does not block in either case (it does, however!). Otherwise, how could it ever be "after", it would have to be "during". MSDN also mentions that shutdown() will not block regardless of whether linger is enabled, but it fails to mention that calling shutdown() actually disables linger. Surprise. There exists another well-hidden page on MSDN -- if you can find it -- which speaks of linger as does not complete immediately, which suggests closesocket() indeed blocks with linger (which it does, too!).
If you only keep searching long enough, you learn that by default Windows does not block on closesocket, but keeps the socket lingering for a graceful shutdown (with no way for you of knowing whether the data was delivered!), but it also supports blocking and abortive close via linger.
POSIX on the other hand side specifies very precisely what happens with linger:
If SO_LINGER is set, the system shall block the calling thread during close() until it can transmit the data or until the time expires. If SO_LINGER is not specified, and close() is issued, the system handles the call in a way that allows the calling thread to continue as quickly as possible.
Except that's not as abvious as one would wish. Every normal-wired person should read this as: If I set SO_LINGER to one, my calls to close() will block, otherwise they will not block. If I don't say anything, the behaviour is probably "no" because I need to do something to enable linger.
The wording of POSIX is also congruent with the wording in Richard Steven's (kinda authorative) book:
If l_onoff is nonzero and l_linger is zero, TCP aborts the connection when it is closed (pp. 1019-1020 of TCPv2). That is, TCP discards any data still remaining in the socket send buffer and sends an RST to the peer, not the normal four-packet connection termination sequence
The Linux documentation, however, states that calling exit() automatically causes any open sockets to linger in the background. Always. What does that mean? Does it mean exit() blocks? That would be funny. Does it mean exit() succeeds immediately but the socket remains (this is what actually happens!)? For how long? Forever? We have no way of knowing, they're not telling us. Well yes, we have a way of knowing, there's a proc thingie for that... but it's not really obvious.
What is the intention behind this complicated mess?
TCP has guaranteed delivery. Once you have successfully passed data to the network stack, you have the guarantee that it will either be delivered, or you will get an error message. How do you get an error? Surely not from send() because at the time send() returns the data is most certainly still inside the send buffer and hasn't even made it to the wire, let alone the target machine. There is no way of telling whether any of the data ever arrives anywhere at this point.
So, someone else must tell you that an error occurred (such as the other host is no longer reachable, user pulled a cable, whatever). That would be the next time you send or receive, or well... once you close the socket. This is your last chance of knowing whether everything went as you expected. Once close() returns, the socket is gone. No more errors, ever again.
Thus, the "correct" behavior of close must be to block (on TCP sockets), by default. That's however not what you conclude from reading either the POSIX or Windows documentation (at least I don't). Blocking indefinitively can be undesirable. If nothing else, it is a huge potential resource leak, and enables a very easy DoS attack on every server.
Therefore, the "next best" behaviour would arguably be to block for some time, and then give up. That's what linger does. Or at least, that's what linger does under POSIX systems. Under Windows, if you trust what MSDN says, the socket stays open, but if errors occur, then that's just bad luck. You never know because closesocket() didn't wait for them. Stevens requires that the call to close() blocks for the specified time, and it returns EWOULDBLOCK in case data was dropped because of timeout.
So what is this good for?
You will almost certainly only ever either use linger with a zero linger time (that is, abortive), or not use it at all and simply let TCP work the way it works by default. Which is (hopefully) the safest, and most desirable way on the average case.
The linger option lets you demand that it waits, and lets you specify for how long. However, telling it "zero" means that it will not wait at all, and closing the socket will not block. In other words, it lets you abort a connection (dropping data) rather than close it. Which... duh... is exactly the behaviour that you actually expected from the beginning.
Luckily, this indeed seems to work consistently pretty much everywhere. At least under Windows, Linux, FreeBSD, and OS X it certainly does.
There might be the temptation to use linger with a non-zero time. I don't recommend doing that since it is not very useful, and also the results are a bit unpredictable. OS X has a somewhat funny idea of what the word "seconds" means, and Cygwin (at least the 1.7.xxx version that I tried) totally fucks up, blocking infinitely.
Posted by samoth on 27 May 2016 - 04:41 PM