Guarantee Critical Regions in Portable code. Portable Semaphores?

I don't want to cause a flame war, but it has to be said: You're just a very rude person (Vladimir), atleast Clifford provided me with some useful information.

Thanks Clifford.

"CBFalconer" wrote: .. snip ...

Thanks for the links, I'm not really used to USENET etiquette.

James

The result of this topic I have concluded is that:

a) Disabling Interrupts cannot necessarilyy provide Atomic operations, and could cause problems in a system that you are not able to make assumptions for.

b) Providing a wrapper to an OS provided semaphore will be much safer, and actually just what I need to do. Implementing semaphores myself would create massive portability problems, especially when trying to ensure atomic operations. Much easier to make use of any existing semaphore system provided by an OS, if any...

c) On systems with no OS and therefore no threads, i.e. Single-threaded applications, these wrapper functions will essentially do nothing. As thread-safety won't be an issue.

Thanks for the information, Its great to have people help you think through your ideas.

James

The code also runs on MIPS and PowerPC, I didn't need more. Did you have a question?

You read the Intel standard, and you deploy it to hundreds of thousands of different uncontrolled commodity PCs, and you observe that the locking works on all of them despite heavy contention.

No, it proves that what it relies on (bus-locked instructions) is reliable.

Unlike your advice, it seems.

Microsoft has/had patents on the FAT implementations too and those covered the 8.3 naming scheme. I'm not positive, but I think I remember seeing that they have let the FAT12 and FAT16 patents lapse.

George

... snip ...

There is no such thing as 'letting patents lapse'. They are issued, and are valid for the patent time (set by law) or until a court declares that patent invalid. As I said before, I suspect any MS patents on the LFN systems have or are about to expire.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.

At least in Europe, you have to pay a fee every year. If you will not pay the fee, the patent will lapse.

Paul

I think in the US it is now 20 years, although it used to be longer. The 20 years might just apply to patents granted since the time limit was changed.

....but then I could be completely wrong.

--
Regards,
Richard.

+ http://www.FreeRTOS.org
Designed for microcontrollers.  More than 7000 downloads per month.

+ http://www.SafeRTOS.com
Certified by TÜV as meeting the requirements for safety related systems.

I have the answers. The only way to ensure the order of the operations is by making them as an assembly function. This is the system level work; the application or driver programmers should make no assumptions and rely on the system services. Especially if they are developing a code which is supposed to be portable.

I observe something that kinda works, until it quits working. Fixing somebody else's hw/sw problems with locking and interrupts provides me the steady income. So, please do more of the unreliable code.

Recommended reading:

Eide, Eric and John Regehr. "Volatiles Are Miscompiled, and What to Do About It," Proceedings of the Eighth ACM and IEEE International Conference on Embedded Software, October 2008,

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

Technically you're right - patents don't lapse, they expire. However, companies routinely make small "improvements" and file a new patent, effectively extending the life of the original patent if they are successful. AFIAK, Microsoft has not done this.

fwiw: my father and sister are both patent attorneys. I did the paralegal thing for a few years and discovered I don't like the nuts and bolts practice of law ... or I'd likely be one too. I should have written more precisely.

George

The US has a similar system for trademarks, but the fee period is a number of years (I think 6 years but I'm not positive).

George

d s

While I will not encourage you to use interrupt masking for atomic operations, it is a viable option in single bus master environments. You mask the interrupt, test and set the flag, unmask the interrupt. Comes at no latency cost worth mentioning. Again, only in address space which will not be accessed by another bus master while the atomic operation is in progress.

But the benefit of doing atomic operations platform independent would be minimal - you probably will not need them at all if your FAT access thing will run under an OS, the latter will take care of this in most cases. And basically doing atomic access is a platform dependent thing, some do it locking the bus for a while, others (PPC) do it by read/write if no access in the meantime/retry otherwise, so spending time on this is just a waste. Even if you have to include it somewhere in your code (e.g. to reserve the piece of hardware holding the filesystem at a sub- driver level), the porting effort on modifying a section of 2-3 lines will be negligible.

Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

Original message:

8.3 naming? That was already in CP/M, and even if it were patented, it would long have expired. So what other distinctive features does FAT have? Hierarchical directories? Everyone did that at the time FAT was introduced. Allocating disk space with linked lists? If I look deep enough in the "Art of Computer Programming" chapter on linked lists, I'll probably find a sentence or two describing the technique used in FAT (storing the list links in a separate area than the actual data blocks).

So what remains is long file names. All the patents listed on relate to that: "Method and system for accessing a file using file names having different file name formats", "Common name space for long and short filenames".

Of course, IANAL and Wikipedia is not legal advice, but I remember doing a little more detailed search a while ago at work, and came to the same conclusion.

Stefan

I normally weigh portability very very high as well, but this is a little too extremistic for my taste.

When I make a codec, my porting layer consists of a header file mapping FFTs, fract multiplications, vector add, etc. to platform-specific assembler sequences, or, if none available, to library routines.

Likewise, a porting layer can consist of a header file mapping atomic operations to platform-specific assembler sequences, or, if none available, operating system routines.

Why should I call two OS services (wait for mutex, release mutex) to implement atomic increment if a simple, much cheaper 'lock inc [address]' also does? Especially in an embedded context, where performance still matters because you cannot always throw more hardware at the problem.

Stefan

It's possible to use assembler in a C or C++ function (carefully marked volatile in the right places), and even sometimes for those functions to be inlined, as I did. But VV is right, you need assembly. It seems you already knew that though.

Non-sequitur. It *is* system-level work, but if you know that the hardware is guaranteed to implement atomic operations all the way down (past caches etc), there's no need to call the operating system kernel.

It's possible to define a small set of atomic operations that can be implemented on a range of common hardware, which allows the callers to be written portably. The reason is simple; if the required features were missing, it wouldn't be possible to write the operating system either.

You don't need to. But you do need to know that your locking is actually behaving as you expect; which is what VV is advising. We're all in violent agreement here.

the steady income.

I'm sure it does. The problem is that of the 1% of programmers who think they know how to write correct multi-threaded code, only 1% actually do ;-) And even they need to be extraordinarily careful, it's difficult stuff to get right.

Clifford Heath.

Trademarks are different from patents (and copyrights) - you have to actively protect them against any abuses you know about, or you lose the right to them.

I've never been able to find any such patents. That doesn't mean that there weren't any, but if you're sure there are, it would be helpful if you were to post the patent numbers.

They have at least three live US patents on FAT filesystem support for long filenames: 5,579,517, 5,758,352, and 6,286,013. As far as I can tell, none of the claims would affect FAT implementations that don't support long filenames.

I don't have cites unfortunately. I am reasonably certain there is something to be found because Microsoft sued Wind River over its DOS compatible file system and Wind River ended up licensing the FAT file system from Microsoft.

It's hard to know what to search for - prior to 1996, software methods, as such, could not be patented (and I don't think they should be patentable at all). Prior to that, software had to be covered as being part of a physical process. So you have to think of things like "an allocation map based system for storing and retrieving diskette files", or whatever, and search accordingly.

It's also possible that patents covering FAT belonged to someone else initially and were bought by Microsoft. Disks were not exactly new when PCDOS emerged and the USPTO collection can't be searched easily prior to 1976.

George

All the techniques used in the FAT file system were already known. That doesn't matter. What matters for a patent is that the expression of the idea be novel - ie. not hinted at by prior art - and that you are first in line to file an application.

The problem is there usually isn't time for a patent examiner to do a thorough search of prior art. In the US, the applicant and attorney are expected to have done that before filing. Average time spent examining an application is 1/2 day. Additionally, US patent examiners cannot reject an application without finding written prior art. It may be the case that there is unwritten history that invalidates the application, but unwritten history does not count.

IANAL George