Linux flash file systems

JFFS2 vs UBIFS
Chris Simmonds 2net Limited Embedded Systems Conference UK. 2009 Copyright 2009, 2net Limited

Overview

Many embedded systems use raw flash chips JFFS2 has been the main choice for almost 10 years As flash sizes increase the scalability problems of JFFS2 become more obvious UBIFS is being talked about as the next flash file system

How does it compare?

Chris Simmonds 2net Ltd

Types of flash memory

NOR NAND Erase block e.g. 128 KiB Page e.g. 2112 B Erase block e.g. 128 KiB Out Of Band area (64 B) Data area (2048 B)
Max erase cycles: 100K to 1M per erase block
Max erase cycles: 10K to 100K per erase block

NAND flash

Bit errors
Need ECC stored in OOB area to detect & correct ECC may be handled in hardware or software

Bad blocks

Up to 2% erase blocks bad in new chips Blocks may go bad during normal operation Bad block marked with a flag on OOB
Multi-Level Cell (MLC) NAND
High storage density; high bit error rate; few erase cycles (10 K)

Flash translation layers

Sub allocation within erase block Garbage collection to coalesce & free obsolete data Wear leveling Bad block handling (NAND)
Includes ECC generation & checking
Avoid data corruption when powered down

Commodity flash devices

For example SD, Compact Flash, USB storage Flash translation layer implemented in firmware on the device
Appears to operating system like a hard drive Some have known problems with wear leveling and corruption at power off
Very limited reliability data from manufacturers
Alternative: use raw flash with translation in the file system
That is what JFFS2 and UBIFS do!

Flash file systems

UBIFS UBI MTD

JFFS2 MTD

Raw flash
Memory Technology Device layer
MTD is the lowest level for accessing flash chips Presents flash as one or more partitions of erase blocks
Character /dev/mtd Block dev /dev/mtdblock

MTD core

SLC NAND

MLC NAND

File data and meta data stored as nodes No index stored on-chip: have to re-create from summary nodes at mount: mount is slow Bad block handling (NAND) Optional data compression - zlib default

Erase block

MTD partition

Used erase blocks

Free erase blocks

Data nodes

Summary node
UBI = Unsorted Block Image Maps Physical Erase Blocks in an MTD partition to Logical Erase Blocks Adds
Bad block handling Volumes Wear leveling within a volume
Introduced in Linux 2.6.22
UBI - erase block mapping
PEB = Physical Erase Block LEB = Logical Erase Block Vol 1 UBI: LEBs Vol 2
MTD partition PEBs Bad block

Journal

Robust on power fail

Write-back cache

Faster writes (see next slide)

On-chip index

Fast mount

Compression: lzo or zlib

More data on your chip!
Introduced in Linux 2.6.27
Consequences of write-back cache
Write-through cache (e.g. JFFS2)
All writes are synchronous
Writes are completed later by pdflush daemon
To avoid loss of data need to do one of
Call fsync() after critical writes Open files with O_SYNC flag Mount ubifs with -o sync

Device used for testing

ARM 926 SoC @ 155 Mhz 64 MiB RAM 1 x 1Gib (128 MiB) ST/Numonyx NAND flash
128 KiB erase block 2 KiB page Software ECC Programmed i/o

2.6.27 kernel

Write test
Write 10 MiB random data in block sizes 4KiB, 64KiB and 1MiB to
Raw device: /dev/mtdblock5 JFFS2 file UBIFS file

Write 10 MiB zeros to

JFFS2 file UBIFS file

Write speed

6.000 5.000 4.000 3.000 2.000 1.000 0.000 4K 64KB 1MB
raw JFFS2/rnd JFFS2/zero UBIFS/rnd UBIFS/zero

Write speed conclusions

Raw speed is 0.7 MiB/s JFFS2

Random data: 0.2 MiB/s

Compression slows it down Compression fast, approaches raw speed

Zeros: 0.7 MiB/s

Random data: 0.8 MiB/s Zeros: 5 MiB/s
Write-back cache speeds up in both cases

Read speed test

Read 10 MiB random data in block sizes 4KiB, 64KiB and 1MiB from
Measure JFFS2 and UBIFS times
Immediately after mount (no data cached) Again, with cache fully primed

Read speed results

18.000 16.000 14.000 12.000 10.000
8.000 6.000 4.000 2.000 0.000 4K 64KB 1MB
raw JFFS2 first JFFS2 again UBIFS first UBIFS again

Read speed conclusions

Raw speed: 1.1 MiB/s Immediately after mount
JFFS2: 0.87 MiB/s UBIFS: 1.0 MiB/s

Subsequently

Both ~15 MiB/s
Not much difference between JFFS2 and UBIFS

Mount time

Mount a file system containing
No files 10 files of 8MiB (partition 80% full) 10,000 files of 8KiB (partition 80% full)

Mount speed

Seconds
empty large files small files

0 JFFS2 UBIFS

Mount time conclusions
UBIFS mount time is constant at 0.5s JFFS2 mount time increases dramatically
Empty: 1.98s 10K small files: 30s
The JFFS2 garbage collector thread runs for up to 90s after mount
Some file operations (e.g. ls *) will be blocked until it completes

Space efficiency

Empty partition with initial size 109312 blocks of 1 KiB
JFFS% overhead 2.46% UBIFS 98004 % overhead 11.54%
Space taken by a file containing 1 MiB random data when written many small pieces and one large piece
JFFS2 Write size Blocks used % overhead 16 bytes 1468 43.36% 1MiB 1048 2.34% UBIFS Blocks used % overhead 1364 33.20% 1365 33.30%

Summary

UBIFS is faster than JFFS2 in all cases
Overwhelmingly so during mount
JFFS2 makes more efficient use of space Conclusion:
Use JFFS2 on small partitions (< 16 MiB) Use UBIFS in other cases

References

The Linux MTD, JFFS2 and UBI project
http://www.linux-mtd.infradead.org/index.html

IN THE UNITED STATES DISTRICT COURT FOR THE SOUTHERN DISTRICT OF ILLINOIS UNITED STATES OF AMERICA, Plaintiff, v. AJIT TRIKHA, and TRX HEALTH SYSTEMS, P.C., Defendants. Case No. 06-CR-30098-DRH MEMORANDUM & ORDER HERNDON, District Judge: I. INTRODUCTION This matter is before the Court on Defendants Amended Motion to Declare 18 U.S.C. 1374; 18 U.S.C. 1341 and 2; 18 U.S.C. 982(a)(7); 18 U.S.C. 981(a)(1)(c); and 28 U.S.C. 2461 Unconstitutionally Vague as Applied to Defendants and to Dismiss the Indictment (Doc. 55). The issues, having been fully briefed by the parties, are now ripe for determination. II. BACKGROUND Defendant Ajit Trikha (Trikha) is a psychiatrist practicing within the Southern District of Illinois (Doc. 28, 1). Trikha incorporated TRX Health
Systems, P.C. (TRX), his codefendant in this case, as an Illinois corporate entity on June 1, 2000 (Id. at 2). Trikha is the President, Secretary and Treasurer of TRX (Id.). Thereafter, on March 5, 2001, Trikha changed his provider payee information Page 1 of 11
to TRX Health Systems, P.C. (Doc. 28, 10). In a Superseding Indictment, issued on October 20, 2006 (Doc. 28), defendants Trikha and TRX (collectively Defendants) were charged with two counts (Counts 1 and 2, Doc. 28, 16-17 and 18-19) of health care fraud in violation of 18 U.S.C. 13471 and one count (Count 3, Doc. 28, 20-22) of mail fraud in violation of 18 U.S.C. 1341 & 1342.2
18 U.S.C. 1347, regarding health care fraud, states: Whoever knowingly and willfully executes, or attempts to execute, a scheme or artifice-(1) to defraud any health care benefit program; or (2) to obtain, by means of false or fraudulent pretenses, representations, or promises, any of the money or property owned by, or under the custody or control of, any health care benefit program, in connection with the delivery of or payment for health care benefits, items, or services, shall be fined under this title or imprisoned not more than 10 years, or both. If the violation results in serious bodily injury (as defined in section 1365 of this title), such person shall be fined under this title or imprisoned not more than 20 years, or both; and if the violation results in death, such person shall be fined under this title, or imprisoned for any term of years or for life, or both.
18 U.S.C. 1341, regarding mail fraud, states: Whoever, having devised or intending to devise any scheme or artifice to defraud, or for obtaining money or property by means of false or fraudulent pretenses, representations, or promises, or to sell, dispose of, loan, exchange, alter, give away, distribute, supply, or furnish or procure for unlawful use any counterfeit or spurious coin, obligation, security, or other article, or anything represented to be or intimated or held out to be such counterfeit or spurious article, for the purpose of executing such scheme or artifice or attempting so to do, places in any post office or authorized depository for mail matter, any matter or thing whatever to be sent or delivered by the Postal Service, or deposits or causes to be deposited any matter or thing whatever to be sent or delivered by any private or commercial interstate carrier, or takes or receives therefrom, any such matter or thing, or knowingly causes to be delivered by mail or such carrier according to the direction thereon, or at the place at which it is directed to be delivered by the person to whom it is addressed, any such matter or thing, shall be fined under this titleor imprisoned not more than 20 years, or both. If the violation affects a financial institution, such person shall be fined not more than $1,000,000 or imprisoned not more than 30 years, or both.

(contd on next page)

Page 2 of 11

Lastly, Count 4 seeks forfeiture of Defendants property, real and personal, to the Government from gross proceeds traceable to the commission of said offenses in the amounts of at least $2,430,768.93 and $10,911.15 (Id. at pp. 8-9). Simply stated, Defendants have been charged with submitting false provider billing claims to both Medicare and Medicaid in order to collect payments they were not entitled to receive. Pursuant to the Superseding Indictment, both Medicare and Medicaid require provider billing claims to include Current Procedural Terminology (CPT) codes to identify the service performed by the provider. These CPT codes are established by the American Medical Association (Doc. 28, 11). The Government charges Defendants with falsely billing for the following services: (1) CPT code 90807 - Individual psychotherapy, insight oriented, behavior modifying and/or supportive, in the office or outpatient facility, requires of approximately 45 to 50 minutes face-to-face with the patient; with medical evaluation and management services.
Regarding CPT code 90807, the Government charges Defendants for billing both Medicare and Medicaid for this code when Trikha spent little or no time with the
(contd from previous page) 18 U.S.C. 1342, also regarding mail fraud, states: Whoever, for the purpose of conducting, promoting, or carrying on by means of the Postal Service, any scheme or device mentioned in section 1341 of this title or any other unlawful business, uses or assumes, or requests to be addressed by, any fictitious, false, or assumed title, name, or address or name other than his own proper name, or takes or receives from any post office or authorized depository of mail matter, any letter, postal card, package, or other mail matter addressed to any such fictitious, false, or assumed title, name, or address, or name other than his own proper name, shall be fined under this title or imprisoned not more than five years, or both.

Page 3 of 11

patient and Defendants also billed for individual psychotherapy services during the time that Trikha was actually out of the country (Id. at 12). (2) CPT code 90853 - Group psychotherapy (other than of a multiple-family group) by a physician, with continuing medical diagnostic evaluation and drug management when indicated.
The Medicare Carrier for Illinois, Wisconsin Physician Services, also requires that the group size should be of a size that can be successfully led (i.e., maximum of 12 people) when submitting a CPT code 90853 billing claim to Medicare. The

Government states that Defendants regularly billed Medicare for CPT code 90853 when the group size far exceeded 12 people and Defendants also billed for group therapy services during the time that Trikha was actually out of the country (Id. at 13). (3) CPT code 90862 - Pharmacologic management, including prescription, use, and review of medication with no more than minimal medical psychotherapy.
The Government, in regards to CPT code 90862, states that Defendants billed both Medicare and Medicaid for this code without meeting with the patient, claiming an in-office visit when the patient was not present, and again, Defendants also billed for in-office pharmacologic services during the time that Trikha was actually out of the country (Id. at 14). (4) CPT code 90817 - Individual psychotherapy, insight oriented, behavior modifying and/or supportive, in an inpatient hospital, partial hospital or residential care setting, approximately 20 to 30 minutes face-to-face with the patient; with medical evaluation and management services.

and Page 4 of 11

CPT code 90819 - Individual psychotherapy, insight oriented, behavior modifying and/or supportive, in an inpatient hospital, partial hospital or residential care setting, approximately 45 to 50 minutes face-to-face with the patient; with medical evaluation and management services. The Government also charges Defendants for billing both Medicare and Medicaid for CPT codes 90817 and 90819 when Trikha spent little or no time with the patient instead of either approximately 20 to 30 minutes as required by CPT code 90817 or approximately 45 to 50 minutes as required by CPT code 90819. Further, the Government states that Defendants submitted these billing claims for visits with patients who were not able to communicate verbally at all (Id. at 15). Defendants now advance the argument that the Superseding Indictment should be dismissed for being unconstitutionally vague as applied to them (Doc. 55). For the following reasons, Defendants Motion must be denied. III. DISCUSSION A. Legal Standard 1. Rule 12(b) Pretrial Motion Defendants Motion to Dismiss is made pursuant to FEDERAL RULE OF CRIMINAL PROCEDURE 12(b)(2), which allows a party to raise any defense, objection, or request that the court can determine without a trial in a pretrial motion. This includes a pretrial motion claiming a defect in the indictment. FED. R. CRIM. P. 12(b)(3)(B). With their Motion, Defendants are not disputing the constitutionality of the statutes on their face. Instead, what is brought into question is the
constitutionality of these statutes as they are applied to Defendants in particular, via Page 5 of 11
the Superseding Indictment. Thus, the Court looks at whether the Superseding Indictment, when coupled with the factual allegations of this matter, vitiates the charging statutes, making them unconstitutional. Under FEDERAL RULE OF CRIMINAL PROCEDURE 7(c)(1), an indictment must be a plain, concise, and definite written statement of the essential facts constituting the offense charged. An indictment will be found sufficient if it (1) contains the elements of the offense charged and fairly informs a defendant of the charge against which he must defend and (2) enables [a defendant] to plead an acquittal or conviction in bar of future prosecutions for the same offense. United States v. Moore, 446 F.3d 671, 676-77 (7th Cir. 2006)(quoting United States v. Webster, 125 F.3d 1024, 1029 (7th Cir.1997))(internal citation omitted). When the validity of an indictment is challenged by a defendant, the reviewing court must view all facts in the light most favorable to the government. United States v. Yashar, 166 F.3d 873, 880 (7th Cir. 1999). The Court should also conduct a practical review of the challenged indictment in [its] entirety, rather than in a hypertechnical manner. United States v. Smith, 230 F.3d 300, 305 (7th Cir. 2000)(quoting United States v. McNeese, 901 F.2d 585, 602 (7th Cir.1990)). 2. Vagueness Doctrine Due process requires that a penal statute be sufficiently definite to give notice to a person of ordinary intelligence of the prohibited conduct, in order for that person to conform his or her conduct within the proscribed legal confines.

Page 6 of 11

Kolender v. Lawson, 461 U.S. 352, 357 (1983). Therefore, one may challenge the constitutionality of a penal statute based upon the argument that the statute is vague, as the [vagueness] doctrine incorporates notions of fair notice or warning. Smith v. Goguen, 415 U.S. 566, 572-73 (1974). Vagueness challenges that do not involve First Amendment freedoms must be analyzed as applied to the specific facts of the case at hand. Maynard v. Cartwright, 486 U.S. 356, 361 (1988); United States v. Lim, 444 F.3d 910, 915 (7th Cir. 2006)(citing United States v. Mazurie, 419 U.S. 544, 550 (1975)). A penal statute may be void for vagueness for either of two independent reasons. City of Chicago v. Morales, 527 U.S. 41, 56 (1999). First, a statute may be unconstitutionally vague if it fails to provide the kind of notice that will enable ordinary people to understand what conduct it prohibits. Id. (citing
Kolender, 461 U.S. at 357). A statute may also be unconstitutionally vague if it fails to provide explicit standards to prevent arbitrary and discriminatory enforcement by those enforcing the statute. Lim, 444 F.3d at 915 (citing Karlin v. Foust, 188 F.3d 446, 458-59 (7th Cir. 1999)). As observed by the United States Supreme Court, the requirement that a penal statute provide minimal guidelines in order to discourage arbitrary enforcement is perhaps the most meaningful aspect of the vagueness doctrine. Smith, 415 U.S. at 574. Without these minimal enforcement guidelines provided within a statute,policemen, prosecutors, and juries [are allowed] to pursue their personal predilections. Id. at Page 7 of 11
575. B. Analysis The crux of Defendants vagueness argument concerns the application of the CPT codes to the facts of this case. Defendants contend that the CPT codes themselves are vague and therefore fail to provide adequate guidance so that a provider may determine whether using certain CPT codes when billing for services rendered is proper or fraudulent. For example, CPT code 90817 is a billing code the provider is advised to use when an individual psychotherapy session is conducted in a nursing home facility, when the provider spends approximately 20 to 30 minutes face to face with the patient. Defendants believe the CPT codes use of the term approximately is vague; they question what the provider should do if he or she only spends 18 or 19 minutes with a patient? Would that provider then be guilty of fraudulent billing if CPT code 90817 were used as the billing code? Also part of their argument is the asserted vagueness of CPT code 90853, which is to be used as a billing code for group psychotherapy sessions by a physician, the requirement that the group size should be of a size that can be successfully led (i.e., maximum of 12 people). Defendants pose the hypothetical of whether a group session could be successfully led if there were 13 people instead of 12 in the group. Would using CPT code 90853 in that situation be considered fraudulent? Defendants further challenge CPT code 90807 (which advises the duration of an individual psychotherapy session), asking if all the goals of an individual psychotherapy session are accomplished in a 30 minute time frame, must the medical provider stay Page 8 of 11

in the room and stare at the walls to fulfill the admonishment that the time spent with the patient should be 45 minutes? (Doc. 55, p. 8). These questions posed by Defendants support their assertion that the vagueness of the CPT codes make it simply impossible for a medical professional to determine what conduct can be considered criminal in nature (Id.). However, Defendants hypotheticals do not accurately portray the allegations in the Superseding Indictment. For instance, Defendants are charged with billing for CPT code 90807 (individual psychotherapy. approximately 45 to 50 minutes face-toface with the patient), when Trikha spent little or no time with the patient. and also billed for in-office psychotherapy services when [he] had traveled outside the United States (Doc. 28, 12). This is a far cry from a situation where the session was 35 minutes. In other words, a rational person would not consider using this CPT code for a session lasting approximately 45 to 50 minutes when that physician had actually spent little or no time with the patient. To do so would definitely put the physician on notice that such an egregious billing would be considered fraudulent. The same holds true for the CPT codes 90817 and 90819 that also require an approximate amount of time spent with the patient. The Superseding Indictment again charges Defendants with regularly billing these CPT codes when Trikha spent little or no time with the patient or billed for visits with patients who were not able to communicate verbally at all (Id. at 15). Again, as applied to these allegations, no rational physician would believe billing under these CPT codes would not likely amount to fraud. Page 9 of 11
Likewise, although Defendants assert that the phrase minimal medical psychotherapy, as used in CPT code 90862, is vague, the Superseding Indictment charges Defendants for regularly billing this code without meeting with the patient, claiming an in-office visit when the patient was not present and billing for in-office pharmacologic management services when [he] had traveled outside the United States (Id. at 14). Clearly, the Court fails to see the shades of grey surrounding the use of minimal when there was absolutely no meeting with the patient. Lastly, Defendants question the definition of the Illinois Medicare requirement that billing for CPT code 90853 (group psychotherapy) that the group size should be of a size that can be successfully led (i.e., maximum of 12 people), asserting it is also vague as applied. Again, however, the Superseding Indictment charges Defendants with regularly billing for that CPT code when the group far exceeded 12 people and also for times when Trikha had traveled outside the United States (Id. at 13). In reviewing the definition, the Court finds no ambiguity in the term maximum, which is generally defined as the upper limit allowed. See Merriam-Websters Online Dictionary, http://www.m-w.com/dictionary/maximum (last visited June 14, 2007). Common sense would dictate that a billing physician with a group far exceed[ing] 12 people should not bill under that particular CPT code, otherwise, it may be improper or fraudulent. In any case, it is not vague as applied to the allegations in the Superseding Indictment. In sum, the Court finds the CPT codes are not ambiguous and vague as

Page 10 of 11

applied to the allegations in this matter. The allegations charge Defendants with behavior that, if proven, clearly do not fall within the definitions for the CPT codes and thus, would provide adequate notice of criminal behavior. The Defendants are reminded that the Government is still required to prove both fraudulent intent in using these CPT codes and that these codes were also improper for the provided services (or for services that were never actually provided). Taking the Superseding Indictment at face value, the Court does not find that the allegations would give pause to any rational physician when determining whether such treatment was properly billable under the CPT codes at issue. In conclusion, the Superseding Indictment is not defective because the charging statutes are not found to be unconstitutionally vague as applied to Defendants.3 IV. CONCLUSION Defendants Motion to Dismiss Superseding Indictment (Doc. 55) is hereby DENIED. IT IS SO ORDERED. Signed this 15th day of June, 2007. /s/ David RHerndon United States District Judge
Although Defendants have cited several cases from sister circuits and districts, the Court finds the analysis for this case to be relatively straightforward and so there is no need to discuss these other nonbinding opinions.

Page 11 of 11