How do iOS devices handle music storage when iTunes Match is enabled? I have an iPhone 3GS 32GB which was packed to the brim with music. Yesterday I signed up for iTunes Match, and I noticed that the Music section of the device settings in iTunes (which used to allow me to select which playlists/songs/genres/artists I wanted synced) has been replaced with this:



iTunes also says my phone has 22.6 GB of free space, despite most of the bar appearing full.



How does my iPhone manage its free space when the device fills up? Will downloaded music automatically be removed when something else needs it, like an app installation or a new podcast? If so, how does it decide what to remove? Or, will I have to manually remove songs one by one if I decide to install all 782 MB of Rage HD again?
Some research led to this article from AllThingsD about how an Apple rep had confirmed that the service does indeed stream the music, but it also saves to the device, thus taking up storage space.  It starts playing before it finishes downloading, but it does actually download and save.

MacRumors and a video from InsanelyGreatMac are somewhat unclear about this, but MacWorld agrees that on an iOS device, it's downloading (scroll down to "Playing iTunes Match songs on your Mac and on iOS").

UPDATE as per comment:
As of iOS 5, the device will delete cached data from apps when it's low on space.  This caused some controversy at first because apps had no way to prevent cached data from being removed automatically.  In the linked article, Marco Arment provides an example:


  A common scenario: an Instapaper customer is stocking up an iPad for a
  long flight. She syncs a bunch of movies and podcasts, downloads some
  magazines, and buys a few new games, leaving very little free space.
  Right before boarding, she remembers to download the newest issue of
  The Economist. (I think highly of my customers.) This causes free
  space to fall below the threshold that triggers the cleaner, which —
  in the background, unbeknownst to her — deletes everything that was
  saved in Instapaper. Later in the flight, with no internet
  connectivity, she goes to launch Instapaper and finds it completely
  empty.


This was fixed in iOS 5.0.1 (Apple Developer documentation) so that developers can differentiate between cached data that is and isn't important.

So, the short version: Once free space gets below a certain level, the device will regain whatever space it can by removing cached data from installed apps.  If it can't do that, or if you're completely out of space, it'll probably just tell you that you don't have enough space to do what you're trying to do.