The Perilous River Crossing

Three missionaries and three cannibals are waiting on the west bank of a river. They have one small boat, which can carry either one or two people. Every trip must have at least one passenger, and anyone in the group—missionary or cannibal—can row. At no time may cannibals outnumber missionaries on either bank where at least one missionary is present. A bank containing only cannibals is allowed. Everyone, along with the boat, must eventually reach the east bank. A crossing means any one-way trip by the boat, including return trips. What is the smallest possible number of crossings?